Fortune's Algorithm

Imagine scattering a handful of seed points across a map. Each point "owns" the region of the map closest to it — no matter where you stand, you belong to the territory of whichever seed is nearest. Stitch those territories together and you get a Voronoi diagram: one of the most useful structures in computational geometry.

Voronoi diagrams show up everywhere — mapping the nearest hospital in a city, routing signals in a sensor network, detecting collisions in a physics engine, or reconstructing surfaces from 3D scan data. Given n seed points, how quickly can we build this diagram?

A naive approach tests every point on the plane against all n seeds: impractical. A smarter brute-force builds each region one boundary edge at a time: $O(n^{2})$. But in 1987, Steven Fortune published an algorithm that does it in $O(n \log n)$ — optimal, because just sorting the seeds already costs that much. His trick is a deceptively simple idea: sweep a line across the plane.

Fortune's algorithm is classified as solved: it achieves the proven lower-bound complexity of Θ(n log n) for Voronoi construction in the algebraic decision-tree model. No algorithm can do better in the worst case.

Click anywhere on the canvas to place seed points, then press Sweep to watch Fortune's algorithm work. The vertical line is the sweep line; the curved arcs below it form the beach line — a frontier of parabolas, one per seed already processed. Every time two beach-line arcs collide or a new seed is hit, the algorithm records a Voronoi edge.

<div class="toolbar">
  <button id="btnSweep" type="button">{{btn_sweep}}</button>
  <button id="btnStep" type="button">{{btn_step}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_clear}}</button>
  <span class="hint-text">{{hint_click_canvas}}</span>
</div>
<canvas id="c" width="500" height="360"></canvas>
<div id="info" class="info-bar">{{info_initial}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; background: #f8f9fb; }
.toolbar { display: flex; gap: .5rem; align-items: center; flex-wrap: wrap; padding: .4rem 0 .5rem; }
button { font: 600 13px system-ui; padding: .38rem .85rem; border-radius: 7px;
         border: 1px solid #1d3557; background: #1d3557; color: #fff; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.hint-text { font-size: .82rem; color: #666; margin-left: .3rem; }
canvas { display: block; border: 1px solid #d0d8e4; border-radius: 8px;
         background: #fff; cursor: crosshair; touch-action: none; max-width: 100%; }
.info-bar { font-size: .88rem; color: #444; margin-top: .45rem; min-height: 1.3em; }

// Code not found

Notice how the regions snap into place as the sweep progresses. The algorithm processes only two kinds of events — site events (the sweep line reaches a seed) and circle events (three arcs meet at a point) — and handles each in $O(\log n)$ time using a priority queue and a balanced binary tree. That is the source of the $O(n \log n)$ total cost.

Building a Voronoi diagram for n seeds sits in a well-understood corner of computational geometry:

• Lower bound: any algorithm that constructs a Voronoi diagram must perform Ω(n log n) comparisons in the worst case (algebraic decision-tree model). The proof reduces sorting to Voronoi — if you could build the diagram faster, you could sort faster, contradicting the Ω(n log n) lower bound for comparison-based sorting.
• Fortune's algorithm achieves the bound: it runs in Θ(n log n) time and $O(n)$ space, making it asymptotically optimal.
• The two event types: a site event fires when the sweep line hits a new seed, adding one parabolic arc to the beach line. A circle event fires when three consecutive arcs become co-circular, collapsing the middle arc and recording a Voronoi vertex. Both are handled in $O(\log n)$ via a heap and a balanced BST.
• Connection to sorting: the tight link between sorting and Voronoi construction is why Fortune's result feels "final" — not just fast, but provably unbeatable.

Fortune's algorithm is intimately related to Delaunay triangulation (the two structures are geometric duals of each other), and it is a canonical example of the sweepline paradigm that underlies many $O(n \log n)$ geometry algorithms.

Voronoi diagrams are one of the most broadly useful data structures in applied geometry, and Fortune's algorithm is the standard way to build them:

• Geographic information systems: nearest-facility queries (closest hospital, fire station, or polling place) are direct Voronoi lookups. Electoral district analysis often uses Voronoi regions as a fairness baseline.
• Mesh generation and finite elements: engineering simulations need high-quality triangular meshes. The Delaunay triangulation — the dual of the Voronoi diagram — produces the "most equilateral" triangles possible, minimizing numerical error.
• Collision detection in games and robotics: Voronoi regions define natural "lanes" through free space. A robot's roadmap through obstacles can be routed along Voronoi edges, maximizing clearance from walls.
• Computer graphics and procedural generation: Worley noise (used for stone, cellular, and alien-skin textures) is directly the Voronoi distance function. Fortune's algorithm underlies efficient texture generation for large scenes.
• Biology and materials science: Voronoi tessellations model cell growth, crystal grain boundaries, and the packing of biological tissue — anywhere territory is claimed by nearest-center dynamics.

Because Fortune's algorithm is provably optimal and runs in linear space, it remains the go-to choice three decades after its publication. Understanding it means understanding the sweepline paradigm that also powers algorithms for closest pairs, interval scheduling, and geometric intersection.

Fortune's algorithm is a rare thing in computer science: a problem with a clean lower bound and an algorithm that meets it exactly. Sorting n numbers can't be done in fewer than Θ(n log n) comparisons, and building the nearest-neighbor partition of a plane can't be done faster either — the two problems are the same problem in disguise.

The sweepline idea — advancing a line across the plane and maintaining just enough state to process events as they arrive — is more than a trick for Voronoi diagrams. It is a general geometric technique that appears again and again in algorithms for closest pairs, intersections, and visibility. Fortune's 1987 paper introduced millions of programmers to the power of trading spatial reasoning for temporal order.

Next time a map app finds your nearest coffee shop in an instant, there's a good chance a Voronoi diagram — and the ghost of Fortune's sweepline — is quietly doing the geometry.