The Sweep Line Paradigm
Sweep line algorithms transform two-dimensional geometric problems into sequences of one-dimensional events. An imaginary vertical line sweeps from left to right across the plane, maintaining a status structure of geometric objects currently intersecting it. Whenever the line hits an event point — a segment endpoint or intersection — the status updates and the algorithm responds. This paradigm powers many of computational geometry's most elegant solutions.
Bentley-Ottmann Algorithm
Given n line segments, finding all k intersections naively requires checking all O(n²) pairs. Bentley and Ottmann's 1979 algorithm does better: it only checks segments that are adjacent in the sweep line's status structure. When two segments become adjacent (due to an insertion or a swap), it tests for intersection and schedules the result as a future event. Total time: O((n + k) log n).
The Event Queue and Status Tree
Two data structures drive the algorithm. The event queue (a priority queue) stores segment endpoints and discovered intersections, ordered by x-coordinate. The status tree (a balanced BST) maintains the vertical order of segments crossing the current sweep line position. This simulator visualizes both structures: the sweep line moves across the canvas while the status tree reorders segments in real time.
Beyond Segments
The sweep line paradigm extends far beyond segment intersection. Fortune used it to compute Voronoi diagrams in O(n log n). The same idea solves rectangle union area, closest pair of points, and Boolean operations on polygons. Understanding the sweep line means understanding a universal technique that appears throughout computational geometry and geographic information systems.