Fortune's algortihm is an incremental approach to contructing a Voronoi diagram of a point set in O(n log n) time and using O(n) space, where n refers to the total number of points.
This is a presentation of the algorithm with an interactive demonstration at the end. Click "Next" to proceed to the next slide or "Skip to Demo" to go straight to the interactive portion.
The method was published in 1987 by Steven Fortune, while he was working at Bell Laboratories. At the time, efficient construction of Voronoi diagrams required the use of complex merge-and-conquer algorithms, and while there were simpler incremental approaches, they could not surpass the O(n2) bound on run time. Fortune's work combined the efficiency of the former with the simplicity of the latter.
Fortune's innovation was the application of a sweeping technique to the problem. The approach already had uses in many computational geometry algorithms, but for Voronoi diagrams, it proved to be not a straightforward task.
Naively sweeping the point set does not work because at any position of the sweepline, the points ahead of the line can affect the diagram behind.
Instead, the author proposed a geometric transformation that allows the sweep to work, although the end result is a distorted diagram with parabolic edges. However, the diagram is topologically-equivalent to the real Voronoi diagram and, as Fortune explains, it is easy to recover one from the other.
While the original algorithm relies on a transformation, it is not the method that caught on in the end. Instead of computing the transformed diagram, modern implementations use a transformed sweepline -- the beachline -- to generate the real diagram directly.
The algorithm still performs a conventional sweep, but instead of sweeping the points, it sweeps events.
The beachline consists of a series of parabolic arcs such that any point on the beachline is equidistant from its nearest site and the sweepline. The points where one arc transitions to the next are called breakpoints and as the beachline grows, they trace out the edges of the diagram.
There are two types of events: site events and circle events, stored in a priority queue by their x-coordinate.
Site events correspond to individual sites in the diagram. They are known in advance. As the sweepline moves past those events, a new arc is generated, creating two breakpoints.
The purpose of circle events is to identify Voronoi vertices where two edges meet and the arc between them collapses. By definition, if there exists an empty circle through any triple of sites, its center is a Voronoi vertex.
Circle events are generated in runtime, when a consecutive triple of sites on the beachline forms a circle with its center ahead of the beachline -- in this case, the potential Voronoi vertex exists outside the completed portion of the diagram. Whether it becomes a real vertex depends on whether the circle is empty.
Recall that sites are processed once the sweepline steps over them. Therefore, the algorithm can confirm the emptiness of the circle only when the sweepline has moved past the circle's rightmost point.
If no new site interferes with the event before it is processed, once the circle's center ends up behind the beachline, the two edges meet and create a Voronoi vertex. In addition, the two sites surrounding the collapsed arc give rise to a new Voronoi edge.
If a new site interferes with a circle event before this occurs, the event is considered to be a false alarm, which is cancelled and never processed. In addition, the two surrounding triples of sites on the beachline are checked for the existence of circle events there.
The diagram is stored in a doubly-connected edge list (DCEL), which is a simple representation of the diagram's topology allowing easy modification and traversal. The data structure keeps track of edges, and typically vertices and faces as well.
Each edge consists of two half-edges, each pointing in the opposite directions. The edges also have pointers to their successors and predecessors, forming a doubly linked list. In this arrangement, each face is bound by a loop of half-edges oriented counterclockwise and every half-edge has a pointer to the face to its left.
For vertices, the data structure records their position in the plane as well as a pointer to an arbitrary incident edge.
The first step is sorting n site events and storing them in a priority queue in O(n log n) time.
The only time an arc can appear on the beachline is due to a site event, and since each event splits one arc in two, the size of the beachline is linear. The beachline is represented by a binary tree. For each site event, an arc lookup and insertion is performed in this tree, so the cost of one such event is O(log n).
Since circle events correspond to Voronoi vertices, and false alarm events are never processed, the algorithm visits a linear number of them. Each circle event is inserted in a priority queue and causes one arc to be deleted from the beachline, both of which take O(log n) time.
Therefore, the overall time complexity of this algorithm is O(n log n).
Click anywhere on the canvas to begin adding points.
Please add five or more points before continuing.
This demonstration is a project made for COMP 163, Fall 2017. It was made possible by the following components and libraries:
Thank you for your attention!