Line Sweep (Segment Intersection)

Jon Bentley & Thomas Ottmann, 1976

Introduced by Jon Bentley and Thomas Ottmann in 1979 (building on Bentley's 1976 sweep-line framework), this algorithm finds all intersections among n line segments by sweeping a vertical line from left to right. Segments enter and leave an active set as the sweep line crosses their endpoints, and intersections are detected among neighboring active segments. The visualization shows the sweep line in gold, active segments in teal, and discovered intersections as coral dots.