Wait, What?
To draw a Voronoi diagram, Fortune’s algorithm tracks a moving frontier made of parabolic arcs that are not part of the final answer.
That is the surprise at the heart of Fortune’s algorithm. The final structure is a set of straight Voronoi edges and vertices, but the sweep process maintains a temporary beach line formed by parabolic arcs. New sites create arcs. Certain triples of arcs disappear at circle events. The traces of those changes become the Voronoi diagram.
It is one of computational geometry’s best lessons in representation: the easiest object to maintain during an algorithm is not always the object you ultimately want.
Quick Answer
Learn Fortune’s algorithm through nearest-site regions → sweep line → parabolic beach line → site events → circle events → event queue → beach-line search structure → Voronoi edges and vertices → invalidated events → robust predicates → O(n log n) complexity → production geometry. Draw the geometry before writing code.
1. Begin With the Voronoi Job
Given a set of sites in the plane, the Voronoi cell of a site contains every point at least as close to that site as to any other. Boundaries occur where two or more sites are equally near.
Applications include facility placement, spatial analysis, meshing, robotics, geographic information systems, nearest-neighbour reasoning and geometric modelling.
The diagram is conceptually simple. Building it efficiently and robustly is not.
2. Sweep the Plane Instead of Comparing Every Pair Everywhere
Fortune’s method moves a horizontal sweep line across the plane. Suppose the line moves from top to bottom. Sites above the sweep line have already been encountered; sites below it have not.
At any moment, some part of the plane is already guaranteed to belong to processed sites. The boundary between that settled region and the unsettled region is the beach line.
3. Why the Beach Line Is Made of Parabolas
For a processed site s and the current sweep line L, consider points that are equally distant from s and L. That locus is a parabola with focus s and directrix L. The beach line is assembled from pieces of these parabolas.
This is the first major conceptual hurdle. Learners often expect the beach line to be a straight front. It is not. Each active site contributes a parabolic arc, and only the lower envelope of those arcs matters.
4. There Are Only Two Kinds of Events
The sweep changes combinatorially at discrete events.
- Site event: the sweep line reaches a new input site. A new beach-line arc is inserted.
- Circle event: three consecutive beach-line arcs become arranged so that the middle arc shrinks to zero. Their corresponding sites define a circle whose lowest point reaches the sweep line. A Voronoi vertex is created.
Everything between events is continuous motion that does not alter the combinatorial structure. That is why the algorithm can use an event queue instead of simulating every tiny sweep movement.
5. Trace a Site Event
Suppose site A is already active and the sweep reaches site B. B creates a new parabola. On the current beach line, find the arc directly above B. That old arc is split into pieces around B’s new arc.
At the breakpoints where neighboring arcs meet, Voronoi edges begin to grow. Those breakpoints move as the sweep continues.
The learner’s tracing table should record: event coordinates, current arc order, inserted or removed arc, neighboring arcs, new edge records and any candidate circle events.
6. Circle Events Create Voronoi Vertices
Take three consecutive arcs corresponding to sites A, B and C. If their breakpoints converge, the middle arc B can disappear. Geometrically, A, B and C define a circumcircle. When the sweep reaches the circle’s lowest point, the disappearance occurs.
The circle center is equidistant from the three sites, so it becomes a Voronoi vertex. Two previously growing Voronoi edges meet there, and a new edge begins.
7. Not Every Scheduled Circle Event Remains Valid
This is one of the most important implementation details. A circle event can be scheduled for an arc, then a later site event can alter the beach line before that circle event occurs. The scheduled event is now stale.
Professional implementations therefore attach events to arcs or maintain validity markers. When an arc’s neighborhood changes, its old candidate circle event is invalidated. When the event later comes off the priority queue, it is ignored if no longer valid.
This is a general algorithmic lesson: priority queues often contain work that has become obsolete. Lazy invalidation can be simpler than deleting arbitrary internal heap elements.
8. The Two Main Data Structures
A textbook Fortune implementation normally needs:
- Event queue: ordered by sweep position. Site events and circle events are processed in order.
- Beach-line structure: an ordered structure that supports finding the arc above a new site and updating local neighbors when arcs split or disappear.
Balanced search trees are commonly used conceptually, though implementation details vary. The hard part is that beach-line order is geometric rather than a fixed numeric key. Searches compare the query x-coordinate against current breakpoint positions determined by the sweep line.
9. Output Representation Matters
A picture is not enough for professional geometry. The result should preserve topology: which edges meet, which cells are adjacent, which edges extend to infinity, and which sites own which faces.
A DCEL-style structure—doubly connected edge list—or another half-edge representation is often appropriate. During the sweep, edge records may be only partially known; endpoints are filled as circle events resolve them.
10. Why the Complexity Is O(n log n)
Each of n site events is processed once. The number of genuine circle events is linear in the final planar structure. Each event performs a constant number of priority-queue and balanced-tree operations costing O(log n), yielding O(n log n) time and O(n) space.
Steven Fortune’s 1987 Algorithmica paper established the sweep-line construction with these worst-case bounds for point sites and related variants.
11. Geometry Is Where Exact Mathematics Meets Floating Point
The clean mathematical description assumes exact comparisons. Real code uses finite-precision arithmetic. Nearly collinear sites, almost coincident circle events and huge coordinate ranges can destabilize naive implementations.
Professional computational geometry separates predicates—questions such as orientation and event ordering—from constructions such as computing coordinates. Robust libraries may use exact or filtered predicates so the combinatorial decisions remain correct even when constructed coordinates are floating point.
The current CGAL manuals are valuable here because CGAL’s design emphasizes efficient and reliable geometric algorithms and kernel predicates rather than assuming ordinary floating-point arithmetic is always sufficient.
12. Voronoi and Delaunay Are Dual—but Keep the Teaching Jobs Separate
For points in general position, connecting sites whose Voronoi cells share an edge gives the Delaunay triangulation. eduKateSengkang already has a dedicated Delaunay-triangulation article. This Fortune article should not re-teach Delaunay construction. Use the duality as a cross-check and conceptual connection.
A professional implementation may compute one structure and derive the other, but canonical teaching ownership remains distinct.
13. A Better Learning Sequence Than “Implement the Whole Sweep”
Programming-education evidence supports beginning with readable worked examples, prediction and tracing before asking novices to write complex code. Fortune’s algorithm particularly benefits from this because the data structure and geometry change together.
First animate or draw three sites. Then trace event order. Then calculate a single parabola breakpoint. Then implement an event queue. Only after those pieces are stable should the learner combine them into a full beach-line structure.
14. Production Validation
- Test one site, two sites and collinear sites.
- Test duplicate or nearly duplicate coordinates according to the chosen input contract.
- Compare output against a trusted geometry library on random point sets.
- Check planar topology, not just rendered pixels.
- Verify each finite Voronoi vertex is equidistant from its incident sites within appropriate tolerance.
- Stress coordinates with large and tiny magnitudes.
- Visualize the sweep during development so stale-event and beach-line errors are inspectable.
Common Failure States
- Thinking the beach line is a straight line.
- Confusing site-event coordinates with circle-event centers.
- Scheduling every three arcs as a circle event without checking geometry.
- Failing to invalidate stale circle events.
- Using a fixed x-coordinate as a permanent beach-line tree key even though breakpoints move with the sweep.
- Producing visually plausible edges with inconsistent topology.
- Assuming ordinary floating point is automatically robust for degenerate inputs.
Practice Ladder
- Beginner: draw Voronoi cells for three and four points by perpendicular bisectors.
- Foundation: derive the focus/directrix parabola used by the beach line.
- Intermediate: hand-trace site and circle events for four sites.
- Advanced: implement event invalidation and a beach-line search structure.
- Professional: emit a topological half-edge structure, add robust predicates, and differential-test against a trusted geometry library.
- Explanation test: explain why the temporary beach line can generate straight Voronoi edges.
Learning Hall Boundary
This article owns Fortune’s sweep-line algorithm for point-site Voronoi construction: the beach line, site events, circle events, event invalidation and robust implementation concerns. It does not replace the existing Delaunay-triangulation article, Bentley–Ottmann sweep-line article, convex-hull material or general computational-geometry foundations.
Evidence Boundary
Steven Fortune introduced the sweep-line method in the 1986 Symposium on Computational Geometry and published the full treatment as “A Sweepline Algorithm for Voronoi Diagrams” in Algorithmica 2 (1987), pp. 153–174, with O(n log n) time and O(n) space for point sites. Current CGAL documentation provides the production context for robust computational geometry and kernel-based predicates. The teaching progression here also draws on programming-education evidence supporting predict/trace/investigate activity and subgoal-labelled worked examples before independent code generation.
Professional rule: you understand Fortune’s algorithm when you can state what the beach line represents, predict exactly when site and circle events change it, and maintain those changes without corrupting geometric topology.
eduKate Sengkang 