the line-sweep paradigm

Imagine a vertical line that you drag from left to right across the plane, passing over every point and every shape exactly once. Instead of comparing all pairs of objects up front, you process objects in the order the sweeping line reaches them, and you only ever compare things that are near the line right now. This left-to-right discipline is the line-sweep paradigm: turn a static 2D problem into a sequence of 1D events processed in order, keeping a small active set of just the objects the sweep line currently touches.

Two ingredients make it work. First, a sorted event schedule: the x-coordinates at which something interesting happens (a point is reached, a segment starts or ends). You process events in increasing x. Second, an active structure (often a balanced search tree or just a sorted set) holding the objects currently crossed by the sweep line, ordered by their y-coordinate, so neighbours in the structure are vertically adjacent. The key insight is that interactions you care about — the closest pair of points, an intersection of two segments — can only happen between objects that are neighbours along the sweep line, so you never need to test far-apart objects. For the closest pair, you sweep left to right keeping points within the current best distance d in a y-sorted set, and for each new point you only compare it to the handful of points within a d-tall window — giving O(n log n) overall. For segment intersections, a crossing can only occur between segments that are adjacent in the y-order, so you check only neighbours as segments enter, leave, and swap, finding all k intersections in O((n + k) log n).

Line sweep matters because it systematically cuts an O(n^2) all-pairs comparison down to O(n log n) or O((n+k) log n) by exploiting locality: only nearby things can interact, and the sweep keeps the nearby things organized. It is one of the most reusable design ideas in computational geometry and beyond, appearing in closest-pair, segment-intersection (Bentley-Ottmann), rectangle-union area, and interval problems. The honest cost is bookkeeping: you must maintain the event queue and the active structure carefully, and degenerate cases (vertical segments, ties in x, multiple events at one coordinate) need deliberate tie-breaking or the sweep mis-orders events.