Fortune's Algorithm (Voronoi Diagram)

Steven Fortune, 1985

Steven Fortune's 1985 sweep-line algorithm constructs a Voronoi diagram in O(n log n) time. A horizontal sweep line moves downward; as it passes each site point, a new parabolic arc is added to the beach line. This simplified visualization reveals Voronoi cells progressively as the sweep line descends: site points appear in coral, cell boundaries in teal, and the sweep line in gold.