Fortune's Algorithm for Voronoi Diagrams
Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
Given a finite set of points (called sites) in a plane, a Voronoi diagram divides the plane into regions around each site that are closer to that site than to any of the others. This Demonstration shows Fortune's algorithm for drawing Voronoi diagrams .[more]
Two auxiliary curves are involved in the procedure:
1. The sweep line (green) can move up or down; only sites above it are active.
2. The beach line (red) is a sequence of parabolic arcs. Each parabola has an active site for its locus and the sweep line as directrix.
The intersections of two parabolic arcs (the breakpoints on the beach line) have equal distance to two sites (the foci of the two parabolas) and to the sweep line. Thus, as the sweep line moves down, these intersection points determine the rest of the diagram.[less]
Contributed by: Erik Mahieu (July 2016)
Open content licensed under CC BY-NC-SA
 S. Fortune, "A Sweepline Algorithm for Voronoi Diagrams," Algorithmica, 2, 1987 pp. 153–174. www.wias-berlin.de/people/si/course/files/Fortune87-SweepLine-Voronoi.pdf.
"Fortune's Algorithm for Voronoi Diagrams"
Wolfram Demonstrations Project
Published: July 19 2016