The Line Sweep Algorithm: Solving Geometry Problems by Sweeping a Line Across the Plane

The Core Idea: A Moving Line and an Active Set

At the heart of line sweep is a wonderfully simple mental picture: an imaginary vertical line gliding from left to right across a plane containing points, line segments, rectangles, or other shapes. Rather than examining how every object interacts with every other object, the algorithm only ever concerns itself with the handful of objects the sweep line is currently touching. This small collection is called the active set, and it is the entire secret to the technique's speed. As the line advances, the active set does not change continuously; it only changes at specific moments called event points, such as where a segment begins, where a segment ends, or where two segments cross. Between events, nothing meaningful happens, so the algorithm can skip straight from one event to the next. Events are typically processed in left-to-right order using a priority queue, while the active set itself is maintained in a data structure that supports fast insertion, deletion, and neighbor queries, most commonly a balanced binary search tree. This combination, an event queue driving updates to an active set, is the skeleton underneath nearly every line sweep algorithm, regardless of the specific geometric problem being solved.

Classic Example: Finding All Segment Intersections

The textbook demonstration of line sweep is detecting every intersection among a set of line segments. As the sweep line moves left to right, it maintains the segments it currently crosses in a balanced binary search tree, ordered by their vertical position, meaning their y-coordinate at the sweep line's current location. Three kinds of events matter: a segment's left endpoint, which inserts it into the tree; a segment's right endpoint, which removes it; and an intersection point, where two segments swap places in the vertical ordering. The crucial insight is that two segments can only newly cross each other if they were adjacent in the vertical ordering just before the crossing happened. A segment far above another in the ordering cannot suddenly cross it without first becoming adjacent to it, since crossing paths must pass through every ordering in between. This means the algorithm never needs to test every pair of segments for intersection. It only needs to check pairs that become adjacent in the tree, whenever a segment is inserted, removed, or swaps position with its neighbor. Each such adjacency check is cheap, and the total number of checks stays proportional to the number of segments plus the number of actual intersections found, making the whole process remarkably efficient even on large, cluttered inputs.

Why This Beats Brute-Force Pairwise Checking

The naive way to find segment intersections is to compare every segment against every other segment, an approach whose running time grows proportional to n squared, where n is the number of segments. Double the input and the work roughly quadruples; with tens of thousands of segments, this becomes painfully slow. The line sweep approach instead achieves a running time proportional to roughly n log n for many practical cases, plus extra time proportional to however many intersections actually exist. The reason for this dramatic improvement is that the sweep only ever compares locally adjacent objects rather than every conceivable pair. Maintaining the active set in a balanced search tree costs time proportional to log n per insertion, deletion, or adjacency swap, and there are only order n such events for the endpoints alone, plus one event per intersection. Instead of asking n squared unnecessary questions like do these two far-apart segments cross, the algorithm asks a much smaller number of meaningful questions, each answerable quickly, precisely because it exploits the geometric fact that far-apart, non-adjacent segments cannot cross without first becoming adjacent.

Other Classic Problems Solved with Line Sweep

Segment intersection is only the most famous use of the technique; line sweep shows up throughout computational geometry. The closest pair of points problem, finding the two points in a set nearest to each other, can be solved by sweeping a line across sorted points while keeping a narrow vertical strip of nearby candidates in the active set, avoiding a full pairwise comparison. Computing the area of a union of overlapping rectangles uses a sweep line that pauses at each rectangle's left and right edges, maintaining a structure that tracks which vertical intervals are currently covered so the covered length can be measured at each event and multiplied by the horizontal distance to the next event. Perhaps the most elegant application is Fortune's algorithm for constructing a Voronoi diagram, which partitions the plane into regions closest to each of a set of input points. Fortune's algorithm sweeps a line across the plane while maintaining a so-called beach line, a chain of parabolic arcs representing the boundary between points already passed by the sweep and the unswept region beyond, with new arcs appearing and old ones vanishing at carefully defined events.

Why the Technique Generalizes So Well

Line sweep is not a narrow trick that happens to work on a few problems; it is a general strategy that succeeds because of a deep structural fact about geometry. Most useful geometric relationships are local, meaning they depend only on nearby objects, and they only change at specific, discrete moments rather than continuously and unpredictably. A segment's neighbors in a vertical ordering do not shuffle randomly; they only swap at well-defined intersection events. A rectangle's contribution to covered area does not fluctuate arbitrarily; it only changes at the rectangle's left and right edges. A Voronoi region's boundary does not warp randomly; it only restructures at specific parabola events. Because change is confined to discrete events, an algorithm never needs to recompute the entire picture from scratch as it scans across the plane. It only needs to react to each event as it arrives, updating a compact active set and moving on. This is why line sweep transfers so readily from segment intersection to rectangle union area to Voronoi diagrams to countless other problems: whenever a geometric problem can be framed as a sequence of local, discrete events sweeping across a coordinate, line sweep is likely to turn a slow, exhaustive approach into a fast, elegant one.

Frequently asked questions

Try it live

Everything above runs in your browser — open The Line Sweep Algorithm: Solving Geometry Problems by Sweeping a Line Across the Plane and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.