The Bentley-Ottmann Sweep

Draw $n$ line segments on a page — road maps, circuit traces, the edges of overlapping polygons — and ask a simple question: where do they cross? The obvious way to answer is to compare every pair of segments, one against another, and check whether they intersect. With $n$ segments that's $\binom{n}{2}$ pairs, so the work grows like $O(n^2)$.

For a handful of segments that's fine. For the millions of edges in a GIS map or a chip layout, quadratic time is a wall. And here's the strange part: most pairs of segments are nowhere near each other, so almost all of that checking is wasted effort on segments that could never possibly cross.

In 1979, Jon Bentley and Thomas Ottmann found a way to only ever compare segments that are genuinely close to each other at some moment — using a line that sweeps across the page and a queue that tells it exactly when to look.

Below is a handful of segments. A vertical sweep line moves left to right; at every moment it only tracks the segments it currently crosses, ordered top to bottom. Only neighbors in that order are ever compared for a crossing.

<p class="hint">{{hint_para}}</p>
<svg id="scene" class="scene" viewBox="0 0 340 220" xmlns="http://www.w3.org/2000/svg"></svg>
<div class="status" id="status">{{status_ready}}</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="log" id="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.scene { width: 100%; max-width: 480px; height: auto; background: #f6f8fa; border: 1px solid #d7dee5; border-radius: 8px; display: block; }
.seg { stroke-width: 2.4; }
.sweep { stroke: #e63946; stroke-width: 1.6; stroke-dasharray: 4 3; }
.dot { fill: #1d3557; }
.cross-dot { fill: #e63946; stroke: #fff; stroke-width: 1; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0 .3rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .5; cursor: default; }
.log { font: 13px ui-monospace, monospace; color: #333; background: #fff; border: 1px solid #e2e6ea;
       border-radius: 8px; padding: .5rem .7rem; max-height: 110px; overflow-y: auto; line-height: 1.5; }
.log .none { color: #888; font-style: italic; }

// Code not found

Press Step to advance the sweep one event at a time, or Run to play it through. Watch how the active order changes only when segments start, end, or swap places at a crossing — that swap is exactly how the algorithm notices an intersection without ever comparing a distant pair.

The trick is to never ask "do these two segments cross?" for a pair that is far apart. Bentley-Ottmann keeps two structures moving together:

• The event queue. A priority queue of $x$-coordinates where something interesting can happen: a segment starts, a segment ends, or two segments cross. It begins with just the $2n$ endpoints and grows as new crossing events are discovered.
• The status structure. A balanced order (conceptually a sorted list, in practice a balanced binary search tree) of the segments currently crossed by the sweep line, ordered by their $y$-coordinate at the line's current position. Only segments that are adjacent in this order are ever tested for intersection.

At each event the sweep does a constant amount of structural work — insert a segment, delete a segment, or swap two neighbors — plus $O(\log n)$ to keep the status structure balanced. Insertions and deletions happen at most $2n$ times (once per endpoint); crossings happen exactly $K$ times, the number of intersection points. So the total number of events is $O(n + K)$, and each costs $O(\log n)$:

$$T(n, K) = O\big((n + K)\log n\big)$$

This is an output-sensitive bound: the running time scales with how many intersections actually exist, not just with $n$. In the worst case $K$ can be $O(n^2)$ (every pair crosses), and the algorithm gracefully degrades to roughly the brute-force bound — but whenever $K$ is small, which is the common case for real maps and drawings, Bentley-Ottmann is dramatically faster than checking every pair. Space stays $O(n)$ for the status and queue, ignoring the room needed to output the crossings themselves. This same insert-delete-swap idea is a workhorse of the broader computational geometry toolbox.

Sweeping a line across geometric data and maintaining order along the way is one of the most reused ideas in applied geometry:

• Geographic information systems (GIS): overlaying two maps — say, roads and rivers — to find every place they meet is exactly the segment-intersection problem, run on millions of edges.
• VLSI design-rule checking: chip layouts are made of enormous numbers of rectangles and wires; checking that none illegally overlap uses sweep-line variants at massive scale.
• Computer graphics: clipping polygons, resolving overlapping shapes, and rendering vector art all lean on sweeping and ordered status structures.
• Robotics and motion planning: detecting where a robot's swept path could collide with obstacles reduces to the same crossing-detection idea.

Once you've seen the sweep line and its event queue here, you've met the pattern behind a whole family of geometric algorithms, including the sweeps used to build a convex hull or a Voronoi diagram.

Bentley-Ottmann answers a deceptively simple question — where do these lines cross? — without ever falling into the trap of comparing every possible pair. By sweeping a line across the plane and keeping only genuinely neighboring segments under comparison, it turns an $O(n^2)$ search into an $O((n+K)\log n)$ one that scales with the number of crossings that truly exist.

It is a small, elegant proof that the shape of an algorithm's work can matter as much as the size of its input — and solved back in 1979, this same sweeping idea still quietly powers the maps, chips and graphics we use every day, sitting alongside classics like the convex hull.