--- title: Sweep-Line Algorithms module: Computational Geometry moduleNumber: 11 lessonNumber: 3 order: 1103 summary: | The plane-sweep paradigm turns a static $2$-D geometry problem into a dynamic $1$-D ordered-set problem: a vertical line sweeps left to right, stopping at an $x$-sorted **event queue** while a balanced-BST **status structure** tracks the objects it currently crosses, ordered by $y$. We derive Bentley–Ottmann segment intersection in $O((n+k)\log n)$, recover closest-pair in $O(n\log n)$, and reduce skyline, rectangle-area, and overlap problems to $\pm1$ event sweeps. topics: [Geometry] sources: - book: CLRS ref: "Ch. 33 — Computational Geometry (§33.2 Segment intersection)" - book: Skiena ref: "§ — Sweepline / Geometry" - book: Erickson ref: "Ch. — (geometry)" practice: - title: 'The Skyline Problem' slug: the-skyline-problem difficulty: Hard - title: 'Rectangle Area II' slug: rectangle-area-ii difficulty: Hard - title: 'My Calendar III' slug: my-calendar-iii difficulty: Hard - title: 'Describe the Painting' slug: describe-the-painting difficulty: Medium --- 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 $\binom{n}{2}$ pairs and costs $\Theta(n^2)$. The **plane-sweep** paradigm avoids the quadratic cost by never considering the whole plane at once: a vertical line sweeps from left to right, and the algorithm tracks only what is _locally_ true at the line's current position.[^clrs-sweep] 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](/algorithms/data-structures/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. > **Remark (The two structures).** > 1. An **event queue**: the $x$-coordinates at which "something happens" > (object endpoints, and, for intersection problems, computed crossing points), > held in sorted order so we can pull the next event cheaply. > 2. A **status structure** (the _active set_): a balanced BST or ordered set > holding exactly the objects the sweep line currently intersects, keyed by > their $y$-coordinate **at the sweep line's $x$**. This $y$-order is the whole > point: vertical neighbors in the status are spatial neighbors in the plane. 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.[^skiena-sweep] > **Remark (Why this is fast).** There are $O(n)$ structural events (two per object), each > costing $O(\log n)$ to process in a balanced status structure, and each event > touches only $O(1)$ _neighbours_. The geometry, the expensive part, is paid > only at events, and only against adjacent objects, never against all pairs. The art in any specific problem is choosing _what counts as an event_ and _what the status orders by_. The rest is bookkeeping. The two structures work in tandem: the **event queue** hands out the next $x$-coordinate to stop at, and at each stop the **status structure** is edited and its new neighbors inspected. The snapshot below freezes one instant — the queue holding the events still to the right of the sweep, and the status holding the three segments the line currently crosses, top to bottom in $y$. $$ % caption: One instant of a sweep: the event queue (sorted upcoming $x$-stops) and the % status structure (active segments, ordered by $y$ at the sweep line). \begin{tikzpicture}[ every node/.style={font=\footnotesize}, >=stealth, x=10mm, y=9mm] \definecolor{acc}{HTML}{2348F2} % --- left: the plane with the sweep line --- \draw[->] (-0.2,0) -- (4.2,0) node[right] {$x$}; \draw[acc, very thick] (2.0,0.1) -- (2.0,3.4); \node[acc] at (2.0,3.7) {sweep}; % three active segments crossing the line, at distinct heights \draw[acc, thick] (0.3,0.9) -- (3.8,1.4); \draw[acc, thick] (0.3,2.9) -- (3.8,1.9); \draw[acc, thick] (0.3,1.7) -- (3.8,2.6); % crossing heights marked on the line (top, middle, low) \fill (2.0,2.3) circle (1.3pt); \fill (2.0,1.85) circle (1.3pt); \fill (2.0,1.15) circle (1.3pt); % --- right: the two data structures as stacked boxes --- \begin{scope}[shift={(5.0,0)}] \node[anchor=west] at (0,3.5) {event queue (by $x$):}; \foreach \i/\lab in {0/{$x_5$}, 1/{$x_6$}, 2/{$x_7$}} { \node[draw, minimum width=8mm, minimum height=5mm] at (\i*0.95+0.4,3.0) {\lab}; } \node[anchor=west] at (0,2.1) {status (by $y$, top down):}; \foreach \i/\lab in {0/{$s_3$}, 1/{$s_2$}, 2/{$s_1$}} { \node[draw, acc, minimum width=8mm, minimum height=5mm] at (0.4,1.5-\i*0.62) {\lab}; } \node[anchor=west] at (1.1,1.5) {top}; \node[anchor=west] at (1.1,0.26) {bottom}; \end{scope} \end{tikzpicture} $$ ## 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.[^clrs-sweep] 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 following invariant collapses the problem from all pairs to a constant check per event. > **Invariant (Adjacency).** Two segments can intersect only after they have become > _adjacent_ in the $y$-ordered status. Just before the crossing $x$, the two > segments meet at the same $y$ and so must be neighbors in the order. 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. $$ % caption: Maintain the $y$-ordered active set; at each event check only neighbors \begin{tikzpicture}[ >=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} % axis \draw[->] (-0.3,0) -- (8.5,0) node[right] {$x$}; % event ticks on the x-axis \foreach \x/\lab in {0.6/{},2.1/{},3.4/{},5.6/{},7.2/{}} \draw (\x,-0.12) -- (\x,0.12); \node[font=\footnotesize] at (0.6,-0.4) {$e_1$}; \node[font=\footnotesize] at (2.1,-0.4) {$e_2$}; \node[font=\footnotesize] at (3.4,-0.4) {$e_3$}; \node[font=\footnotesize] at (5.6,-0.4) {$e_4$}; \node[font=\footnotesize] at (7.2,-0.4) {$e_5$}; % the sweep line \draw[acc, very thick] (4.3,0) -- (4.3,4.3); \node[acc, font=\footnotesize] at (4.3,4.6) {sweep}; % segments currently crossing the sweep line (active) -- accented \draw[acc, thick] (2.1,1.0) -- (7.2,2.3); \draw[acc, thick] (3.4,3.6) -- (6.4,1.4); \draw[acc, thick] (0.6,2.0) -- (5.6,3.4); % a segment not yet reached / already passed (inactive) -- plain \draw (5.6,0.5) -- (8.2,3.0); \draw (0.6,3.8) -- (2.6,4.1); % mark crossings on the active set as small dots \fill (4.3,1.83) circle (1.3pt); \fill (4.3,2.6) circle (1.3pt); \fill (4.3,3.1) circle (1.3pt); \end{tikzpicture} $$ The accented segments form 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. $$ % caption: At crossing $c$ the two segments swap status order, exposing two new % adjacencies to test \begin{tikzpicture}[ >=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} % LEFT panel: status order just BEFORE the crossing (s above t, not yet crossed) \node[font=\footnotesize] at (1.5,3.5) {before $c$}; \draw[black, thick] (0.2,3.0) -- (3.2,3.0) node[right, font=\footnotesize, black] {$u$}; \draw[acc, thick] (0.2,2.3) -- (3.2,1.65) node[right, font=\footnotesize] {$s$}; \draw[acc, thick] (0.2,0.6) -- (3.2,1.15) node[right, font=\footnotesize] {$t$}; % sweep strictly LEFT of the crossing; s is genuinely above t here \draw[black, dashed] (1.4,0.2) -- (1.4,3.3); \node[black, font=\footnotesize] at (1.4,-0.1) {sweep}; % crossing point c lies to the right, not yet reached \fill[red!75!black] (3.9,1.4) circle (1.6pt); \node[red!75!black, font=\footnotesize] at (4.05,1.5) {$c$}; % arrow to the right panel \draw[->, black, thick] (4.2,1.8) -- (5.0,1.8); % RIGHT panel: status order just AFTER the crossing (s and t swapped) \begin{scope}[xshift=5.4cm] \node[font=\footnotesize] at (1.5,3.5) {after $c$}; \draw[black, thick] (0.3,3.0) -- (3.2,3.0) node[right, font=\footnotesize, black] {$u$}; \draw[acc, thick] (0.3,1.3) -- (3.2,2.2) node[right, font=\footnotesize] {$t$}; \draw[acc, thick] (0.3,1.5) -- (3.2,0.7) node[right, font=\footnotesize] {$s$}; % the two newly adjacent pairs to test \node[red!75!black, font=\footnotesize, align=center] at (1.6,-0.25) {new adjacencies:\\(u, t) and (s, below)}; \end{scope} \end{tikzpicture} $$ > **Lemma (correctness sketch).** Every crossing pair is reported. _Proof idea._ > At the moment two segments cross they are equal in $y$, hence adjacent in the > status immediately before. Adjacency arises only at an event, and we test every > pair made adjacent at every event; so the pair is tested before its crossing is > reached, scheduled as an event, and reported when the sweep arrives. $\qed$ We keep the implementation at this level: the careful part is degeneracy (vertical segments, three segments through a point) and reliable [orientation tests](/algorithms/computational-geometry/geometric-primitives), which the references treat in full. ::impl{algo="segment_intersection"} ## Closest pair, swept The [Selection lesson](/algorithms/divide-and-conquer/selection) 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.[^erickson-geom] 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\,]$. > **Remark (Why $O(1)$ comparisons per point).** The survivors lie in a $\delta \times > 2\delta$ rectangle to the left of $p$. By the packing argument from the > closest-pair proof, any such rectangle holds $O(1)$ points (no two can be closer > than $\delta$), so the $y$-window query returns a constant number of candidates. 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. Trace the eviction on the five points $A(0,1)$, $B(1,4)$, $C(2,2)$, $D(6,3)$, $E(7,1)$, swept in $x$-order. After processing $A, B, C$ the best distance is $\delta = \dist(A, C) = \sqrt{4+1} = \sqrt 5 \approx 2.24$ (closer than $A$–$B$ or $B$–$C$). Now $D$ arrives at $x = 6$. Every active point with $x < 6 - \delta \approx 3.76$ is evicted — that is $A$, $B$, and $C$, all three — because none can be within $\delta$ of $D$ horizontally. The $y$-window query around $D$ returns nothing, so $\delta$ is unchanged. When $E$ arrives at $x = 7$, only $D$ survives the $x = 7 - \delta$ cutoff, and $\dist(D, E) = \sqrt{1+4} = \sqrt 5$ ties but does not beat $\delta$. The closest pair is $A$–$C$, found without ever comparing the left cluster against the right one — the eviction did that pruning for free. $$ % caption: Closest pair: only the $\delta\times2\delta$ box left of $p$ (width $\delta$, % height $2\delta$) can beat $\delta$, and it holds $O(1)$ points. \begin{tikzpicture}[ every node/.style={font=\small}, dot/.style={circle, fill, inner sep=1.4pt}, >=stealth] \definecolor{acc}{HTML}{2348F2} \fill[acc!8] (3.8,0) rectangle (5,4); \draw[acc, thick] (3.8,1.3) rectangle (5,3.7); \draw[acc, very thick] (5,0) -- (5,4.2); \node[acc, font=\footnotesize] at (5,4.5) {sweep at $p_x$}; \draw[->] (0.2,0) -- (6.2,0) node[right] {$x$}; \node[dot, fill=acc, label={[label distance=1pt]above right:$p$}] (p) at (5,2.5) {}; \node[dot] (s1) at (4.3,2.0) {}; \node[dot] (s2) at (4.0,3.2) {}; \draw[dashed] (p) -- (s1); \draw[dashed] (p) -- (s2); \node[dot, fill=black!45, label=below:evicted] at (1.5,2.5) {}; \draw[<->] (3.8,-0.45) -- (5,-0.45); \node[font=\footnotesize] at (4.4,-0.85) {width d}; \draw[<->] (5.3,1.3) -- (5.3,3.7); \node[font=\footnotesize, anchor=west] at (5.4,2.5) {height 2d}; \end{tikzpicture} $$ ::impl{algo="closest_pair_sweep"} ## 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. ```algorithm caption: $\textsc{Max-Overlap}(\{[\ell_i, r_i)\})$ — sweep $\pm1$ events $E \gets \varnothing$ for each interval $[\ell_i, r_i)$ do add event $(\ell_i, +1)$ to $E$ // begins add event $(r_i, -1)$ to $E$ // ends sort $E$ by coordinate; break ties with $-1$ before $+1$ $cur \gets 0;\ best \gets 0$ for each event $(x, \delta)$ in $E$ do $cur \gets cur + \delta$ $best \gets \max(best, cur)$ return $best$ ``` 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. Trace it on the three intervals $A=[1,5)$, $B=[2,7)$, $C=[3,5)$. The six events, sorted (with $-1$ before $+1$ at ties), and the running sum are: | coord | $\delta$ | interval | $cur$ after | $best$ | | --- | --- | --- | --- | --- | | $1$ | $+1$ | $A$ begins | $1$ | $1$ | | $2$ | $+1$ | $B$ begins | $2$ | $2$ | | $3$ | $+1$ | $C$ begins | $3$ | $3$ | | $5$ | $-1$ | $A$ ends | $2$ | $3$ | | $5$ | $-1$ | $C$ ends | $1$ | $3$ | | $7$ | $-1$ | $B$ ends | $0$ | $3$ | The peak $best = 3$ occurs on $[3, 5)$, where all three intervals overlap — exactly the segment the figure below highlights. Note the two $-1$ events at coordinate $5$: because $A$ and $C$ both end there and no interval begins, the running sum drops cleanly from $3$ to $1$ without a phantom bump. $$ % caption: Sweep $\pm1$ events to track coverage; the peak is the max overlap \begin{tikzpicture}[ >=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} % three stacked intervals on a timeline \draw (1,3.0) -- (5,3.0); \node[font=\footnotesize] at (0.6,3.0) {$A$}; \draw (2,2.5) -- (6.5,2.5); \node[font=\footnotesize] at (1.6,2.5) {$B$}; \draw (3,2.0) -- (4.5,2.0); \node[font=\footnotesize] at (2.6,2.0) {$C$}; % +1/-1 markers at the endpoints (text mode: math minus garbles) \node[font=\footnotesize] at (1,3.3) {+1}; \node[font=\footnotesize] at (5,3.3) {-1}; \node[font=\footnotesize] at (2,2.8) {+1}; \node[font=\footnotesize] at (6.5,2.8) {-1}; \node[font=\footnotesize] at (3,2.3) {+1}; \node[font=\footnotesize] at (4.5,2.3) {-1}; % timeline axis \draw[->] (0.5,0) -- (7.2,0) node[right] {$x$}; \foreach \x in {1,2,3,4.5,5,6.5} \draw (\x,-0.1) -- (\x,0.1); % running coverage step function beneath \draw[thick] (1,0.4) -- (2,0.4) -- (2,0.8) -- (3,0.8) -- (3,1.2) -- (4.5,1.2) -- (4.5,0.8) -- (5,0.8) -- (5,0.4) -- (6.5,0.4) -- (6.5,0); % highlight the peak coverage segment \draw[acc, very thick] (3,1.2) -- (4.5,1.2); \node[acc, font=\footnotesize] at (3.75,1.5) {cur = 3}; \end{tikzpicture} $$ ::impl{algo="interval_sweep"} **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)$. ::impl{algo="skyline"} **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 — the same coordinate-compressed segment tree from the [Fenwick & Segment Trees](/algorithms/data-structures/fenwick-and-segment-trees) lesson. The area is the sum over slabs of (covered $y$-length) $\times$ (slab width): $$ \text{area} \;=\; \sum_{\text{slabs}} \covered_y(\text{slab}) \cdot \parens{x_{i+1} - x_i}. $$ With $n$ rectangles there are $2n$ $x$-events and $O(n)$ distinct $y$-values, so the sweep runs in $O(n\log n)$. $$ % caption: Rectangle-union area: a vertical sweep accumulates covered $y$-length times % slab width \begin{tikzpicture}[ every node/.style={font=\small}, >=stealth, scale=0.8] \definecolor{acc}{HTML}{2348F2} \fill[acc!15] (0,0) rectangle (4,3); \fill[acc!15] (2,1.5) rectangle (6,4.5); \fill[acc!15] (3,0.5) rectangle (7,2); \draw (0,0) rectangle (4,3); \draw (2,1.5) rectangle (6,4.5); \draw (3,0.5) rectangle (7,2); \draw[->] (-0.4,0) -- (7.8,0) node[right] {$x$}; \draw[->] (-0.4,0) -- (-0.4,5.0) node[above] {$y$}; \draw[acc, very thick] (3.5,0) -- (3.5,5.0); \node[acc, font=\footnotesize] at (3.5,5.3) {slab}; \draw[acc, line width=2.6pt] (3.5,0) -- (3.5,4.5); \node[acc, font=\footnotesize, anchor=west] at (3.75,4.85) {covered = 4.5}; \node[font=\footnotesize] at (1.0,2.7) {$R_1$}; \node[font=\footnotesize] at (5.4,4.0) {$R_2$}; \node[font=\footnotesize] at (6.6,1.2) {$R_3$}; \end{tikzpicture} $$ ::impl{algo="rectangle_area"} ## Optimal intersection and the sweep's reach Bentley and Ottmann introduced the segment-intersection sweep in 1979, and its $O((n+k)\log n)$ bound is the one the textbooks teach.[^bo] But that bound is not optimal: the $\log n$ multiplies the _output_ $k$ as well as the input, so on a set with $k = \Theta(n^2)$ crossings the sweep costs $\Theta(n^2\log n)$, a full log factor above the $\Theta(n^2)$ needed just to list the answer. The natural target is $O(n\log n + k)$ — the sort, plus constant work per reported crossing. That optimum was reached in stages. Chazelle and Edelsbrunner (1992) gave the first $O(n\log n + k)$ algorithm, though it needed $O(n)$ working space and an intricate construction.[^ce] Balaban (1995) then produced a cleaner deterministic $O(n\log n + k)$-time, $O(n)$-space algorithm, and simple randomized incremental methods hit the same expected bound.[^balaban] The lesson's Bentley–Ottmann sweep remains the one to reach for in practice: it is simple, its $\log n$ overhead is negligible unless crossings are dense, and its status-structure idea is the reusable part. $$ % caption: The segment-intersection bounds: naive all-pairs, the Bentley--Ottmann sweep, % and the optimal output-sensitive result. \begin{tikzpicture}[>=Stealth, font=\footnotesize, b/.style={draw, minimum height=8mm, minimum width=34mm, align=center}] \definecolor{acc}{HTML}{2348F2} \node[b] (naive) at (0,1.6) {all pairs\\quadratic $n^2$}; \node[b, draw=acc] (bo) at (0,0) {Bentley-Ottmann\\$O((n+k)\log n)$}; \node[b] (opt) at (0,-1.6) {Balaban / Chazelle-E.\\$O(n\log n + k)$}; \draw[->] (naive) -- (bo); \draw[->] (bo) -- (opt); \node[anchor=west, black] at (2.6,0.8) {drop the all-pairs test}; \node[anchor=west, black] at (2.6,-0.8) {shave $\log n$ o\/f\/f $k$}; \end{tikzpicture} $$ The plane-sweep paradigm reaches far past intersection. The same left-to-right line with an ordered status structure builds the **Voronoi diagram** of $n$ sites in $O(n\log n)$ via Fortune's algorithm (1987), where the status is the parabolic "beach line" and events are site arrivals and arc disappearances.[^fortune] It also drives **Delaunay triangulation**, trapezoidal decomposition, and map overlay — the core tools behind the [proximity structures](/algorithms/computational-geometry/polygons-and-proximity) in the next lesson. Once a problem's answer changes only at a discrete set of $x$-coordinates and depends only on locally adjacent objects, the sweep is almost always the right approach. ## 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\times2\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**. [^clrs-sweep]: **CLRS**, Ch. 33 — Computational Geometry (§33.2): the sweep with an event queue and a $y$-ordered status, and segment-intersection in $O(n\log n)$. [^skiena-sweep]: **Skiena**, § — Sweepline / Geometry: plane-sweep as a general technique; events advance a status structure tracking active objects. [^erickson-geom]: **Erickson**, Ch. — (geometry): closest-pair and the packing argument bounding a $\delta$-rectangle to $O(1)$ points. [^bo]: Jon L. Bentley and Thomas A. Ottmann, "Algorithms for Reporting and Counting Geometric Intersections," _IEEE Transactions on Computers_ C-28(9), 1979 — the original $O((n+k)\log n)$ segment-intersection sweep. [^ce]: Bernard Chazelle and Herbert Edelsbrunner, "An Optimal Algorithm for Intersecting Line Segments in the Plane," _Journal of the ACM_ 39(1), 1992 — the first $O(n\log n + k)$-time output-sensitive algorithm. [^balaban]: Ivan J. Balaban, "An Optimal Algorithm for Finding Segments Intersections," _Proc. 11th Symposium on Computational Geometry_, 1995 — a deterministic $O(n\log n + k)$-time, $O(n)$-space algorithm. [^fortune]: Steven Fortune, "A Sweepline Algorithm for Voronoi Diagrams," _Algorithmica_ 2, 1987 — the beach-line sweep computing the Voronoi diagram of $n$ sites in $O(n\log n)$.