Sweep-Line Algorithms

A great many geometric problems share an awkward shape: they ask a question about $n$ objects scattered in the plane whose answer seems to depend on every pair of objects at once. Do any two of these $n$ segments cross? What is the area covered by the union of these $n$ rectangles? The brute-force answer compares all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs and costs $\Theta (n^2)$. The plane-sweep paradigm dismantles that quadratic by refusing to look at the whole plane at once. Instead it imagines a vertical line sweeping steadily from left to right, and tracks only what is locally true at the line's current position.¹

The payoff is a recurring reduction: a hard $2$-D problem becomes a sequence of cheap updates to a one-dimensional ordered set. At any instant, the only objects that matter are the ones the sweep line currently crosses, and among those, only the ones adjacent in $y$ can interact. We have already built every tool this needs: balanced BSTs and ordered sets from the Balanced Trees lesson, Fenwick and segment trees from the structures that follow, and the sweep is the paradigm that puts them to geometric work.

The plane-sweep paradigm

Every sweep-line algorithm is assembled from two data structures and one loop.

The loop is then uniform. Pop the leftmost event; it marks a combinatorial change: an object enters the active set, an object leaves it, or two active objects swap $y$-order. Update the status structure accordingly, inspect the few neighbors the change could affect, and emit any answers. Between events nothing in the active set changes order, so we never need to look there.²

The art in any specific problem is choosing what counts as an event and what the status orders by. The rest is bookkeeping.

Segment intersection: Bentley–Ottmann

Given $n$ line segments, report all $k$ pairs that cross. The naive test of every pair is $\Theta (n^2)$, wasteful when $k$ is small. The Bentley–Ottmann sweep does it in $O((n+k)\log n)$ by exploiting a single geometric fact.¹

Sweep a vertical line left to right. The status structure holds the segments currently straddling the line, ordered by the $y$-coordinate at which each segment meets the line. As the line advances this order is stable except at three kinds of event:

• Left endpoint of a segment: insert it into the status at its $y$-position.
• Right endpoint: delete the segment from the status.
• Intersection point of two segments: the two segments swap their relative order in the status (the one that was above is now below).

The engine is the following invariant, which collapses the problem from all pairs to a constant check per event.

So at each event we test only the handful of newly-adjacent pairs for a future crossing, and any crossing we find is pushed into the event queue as a new event:

• On insert, the new segment acquires an upper and a lower neighbor; test each of those two pairs.
• On delete, the departing segment's old neighbors become adjacent; test that one new pair.
• On a swap, the two swapping segments acquire new outer neighbors; test those two new pairs.

The accented segments are exactly the active set; the sweep line meets them at three $y$-values, and the status stores them in that vertical order. Because the total number of events is $n$ endpoints plus $k$ intersections, and each costs $O(\log n)$ for the ordered-set operations, the total is $O((n+k)\log n)$ — a decisive win over $\Theta (n^2)$ whenever $k=o(n^2/\log n)$.

The swap event is the subtle one. Two segments $s$ and $t$ are adjacent in the status, $s$ above $t$, until the sweep reaches their crossing $c$; at that $x$ they meet at equal $y$, and just past it their order in the status flips — $t$ is now above $s$. The swap exposes two new adjacencies (the segment $u$ formerly outside $s$ now neighbors $t$, and the segment below $t$ now neighbors $s$), and those are the only pairs worth testing next.

We keep the implementation at this level: the careful part is degeneracy (vertical segments, three segments through a point) and reliable orientation tests, which the references treat in full.

Closest pair, swept

The Selection lesson found the closest pair of $n$ points by divide-and-conquer in $O(n\log n)$. A sweep gives the same bound with a different, often simpler, mechanism, and it generalizes the narrow strip trick of that proof into a running invariant.³

Sort the points by $x$ and sweep. Let $\delta$ be the smallest distance found so far. Keep the points whose $x$ lies within $\delta$ of the sweep line in a balanced set ordered by $y$. When the sweep reaches a new point $p$:

• Evict from the set every point more than $\delta$ to the left of $p$ in $x$.
• Among the survivors, only those within $\delta$ of $p$ in $y$ can beat $\delta$, so query the set for the $y$-window $[p_y-\delta ,p_y+\delta ]$.

Each point triggers one insertion, $O(1)$ deletions amortized, and an $O(\log n)$ range query returning $O(1)$ points to test — so $O(n\log n)$ overall, dominated by the initial sort. The sweep makes the strip dynamic: rather than recomputing a fresh strip at each recursion, it slides one along, inserting and evicting at the boundary.

Interval and rectangle sweeps

The practice problems are sweeps in disguise, and they reveal a simpler status structure than a full BST: when objects are axis-aligned, events are $+1/-1$deltas and the status is a count or a segment tree.

Maximum overlap (My Calendar III, Describe the Painting). Given intervals $[{\ell }_i,r_i)$, find the maximum number covering any point — or the coverage profile. Emit a $+1$ event at each ${\ell }_i$ and a $-1$ event at each $r_i$, sort the events by coordinate, and sweep a running sum. The running sum is the number of intervals covering the current coordinate; its maximum is the answer.

The tie-break matters: at a shared coordinate, ending an interval before starting the next reflects half-open $[\ell ,r)$ intervals and avoids spuriously counting an endpoint touch as an overlap. To describe the painting rather than only its peak, emit a coverage segment between consecutive distinct event coordinates whenever $cur>0$, merging equal-$cur$ neighbors. The sweep costs $O(n\log n)$ for the sort and $O(n)$ for the pass.

Skyline. Given $n$ buildings as $(\ell ,r,h)$, output the silhouette of their union. Sweep $x$-events at building edges; the status is a multiset of active heights. At a left edge insert $h$; at a right edge remove it. After each event the current skyline height is the multiset's maximum, and a key point is emitted whenever that maximum changes. A balanced multiset (or a heap with lazy deletion) gives $O(n\log n)$.

Union of rectangle areas (Rectangle Area II). Sweep a vertical line across $x$-events at rectangle left and right edges. The status tracks, for the current $x$-slab, the total length of $y$ covered by at least one active rectangle. Each rectangle contributes a $+1/-1$ on its $y$-interval at its left/right edge; a segment tree over compressed $y$-coordinates maintains the covered length under these interval updates in $O(\log n)$ each, exactly the coordinate-compressed segment tree from the Fenwick & Segment Trees lesson. The area is the sum over slabs of (covered $y$-length) $\times$ (slab width):

With $n$ rectangles there are $2n$ $x$-events and $O(n)$ distinct $y$-values, so the sweep runs in $O(n\log n)$.

Takeaways

• The plane-sweep paradigm reduces a $2$-D geometry problem to a $1$-D ordered-set problem by advancing a vertical line through an $x$-sorted event queue while a status structure holds the objects crossing the line, ordered by $y$.
• The geometry is paid only at events and only against adjacent objects in the status, turning $\Theta (n^2)$ all-pairs work into near-$O(n\log n)$ sweeps.
• Bentley–Ottmann reports all $k$ segment crossings in $O((n+k)\log n)$: events are endpoints plus discovered intersections, and the adjacency invariant means only neighboring segments can next cross.
• Closest pair sweeps a dynamic $\delta$-strip — a balanced $y$-set queried in a $\delta \times 2\delta$ window holding $O(1)$ points — for $O(n\log n)$.
• Interval and rectangle sweeps use $+1/-1$ events: a running sum gives maximum overlap and coverage, a multiset gives the skyline, and a segment tree over compressed $y$ gives the union of rectangle areas.