Fortune's algorithm

[1][2] It was originally published by Steven Fortune in 1986 in his paper "A sweepline algorithm for Voronoi diagrams.

At any time during the algorithm, the input points left of the sweep line will have been incorporated into the Voronoi diagram, while the points right of the sweep line will not have been considered yet.

Mathematically, this means each parabola is formed by using the sweep line as the directrix and the input point as the focus.

The algorithm itself then consists of repeatedly removing the next event from the priority queue, finding the changes the event causes in the beach line, and updating the data structures.

As there are O(n) events to process (each being associated with some feature of the Voronoi diagram) and O(log n) time to process an event (each consisting of a constant number of binary search tree and priority queue operations) the total time is O(n log n).