Line Sweep Technique

A paradigm that solves geometric problems by moving an imaginary line across the plane and processing events in order.

The paradigm

A sweep-line algorithm imagines a vertical line moving left to right across the plane. Interesting things happen only at discrete event points (segment endpoints, intersections). Between events the combinatorial structure is unchanged, so the algorithm sorts events by x and processes them while maintaining a status structure of objects currently crossing the line, usually a balanced BST ordered by y.

Segment intersection

The Bentley-Ottmann algorithm reports all k intersections among n line segments in O((n + k) log n). Events are segment starts, ends, and discovered intersections. Only segments adjacent in the y-order can intersect next, so each event inserts, deletes, or swaps neighbors and checks the newly adjacent pairs, adding future intersection events to a priority queue.

Event loop sketch

import heapq
events = []  # (x, type, data)
for seg in segments:
    heapq.heappush(events, (seg.x_left,  'start', seg))
    heapq.heappush(events, (seg.x_right, 'end',   seg))
while events:
    x, kind, data = heapq.heappop(events)
    # update the y-ordered status BST; test new neighbors for crossings
    ...

Other sweep problems

• Closest pair of points in O(n log n) with a sliding y-ordered set.
• Union area and perimeter of axis-aligned rectangles with a segment-tree status.
• Rectangle overlap counting and the skyline problem.
• Voronoi diagrams via Fortune's parabolic-front sweep.

Design checklist

Identify the event types, choose a status structure that supports the neighbor queries you need, and sort events with a total order that breaks ties consistently. Robustness usually hinges on exact orientation and comparison predicates, as in computational geometry basics.