FORTUNE'S SWEEP the Voronoi diagram, drawn by a moving line
A Voronoi diagram carves the plane into the region nearest each site — the map behind “which store is closest,” mesh generation, and nature’s cracked patterns. Fortune builds it in O(n log n) by sweeping a line down the plane, tracking a “beach line” of parabolas whose breakpoints trace the Voronoi edges.
THE TECHNIQUE a sweep line and a beach of parabolas
Sweep a line down. Each site above it owns a parabola (points equidistant from the site and the line); their upper envelope is the beach line, and where two parabolas meet traces a Voronoi edge. Site events add arcs; circle events remove one and fix a Voronoi vertex. Below: the finished diagram; click to add sites. live demo
HISTORY & CREDIT an old diagram, a clever sweep
“Fortune invented Voronoi diagrams” — he invented gave a fast way to build them; the diagram is centuries old. cited
1644 / 1850 / 1908 · Descartes sketches them; Dirichlet studies them; Georgy Voronoy gives the general treatment — the diagram’s real ancestry. 1975 · Shamos & Hoey prove Voronoi diagrams can be built in O(n log n) (divide-and-conquer) — the optimal bound, before Fortune. 1986 · Steven Fortune gives the sweepline — same O(n log n), but simpler to implement and reason about, with the memorable beach-line picture. the dual · connect sites whose regions touch and you get the Delaunay triangulation (Delaunay 1934) — the same information, flipped.
Three Voronoi regions meet at the circumcenter of their three sites — equidistant from all three. Fortune 1986 / bound Shamos-Hoey 1975
RECOMMEND FOR I-13 f64 predicates + an event heap
The geometric core is f64 and the event queue is a heap on the array — and the meeting point of three regions comes out exactly:
$ i13 run fort.i13 # sites (0,0) (4,0) (1,3)
Voronoi vertex = circumcenter (2, 1) # equidistant, r = sqrt(5)
Recommend: the arithmetic runs — the parabola breakpoints and the circle-event circumcenter are f64 (verified vertex (2,1)), and the event priority queue is a binary heap on an f64 array (PS-005, closed by dart 062). The strain is the beach line: a balanced ordered structure of arcs — the pointer wall (PS-015), the same one the search trees hit. Note: the simplest correct Voronoi (nearest-site colouring, O(n) per pixel) needs nothing at all — the demo above; Fortune is the fast build, and only its beach line reaches past the array.