Voronoi Diagram construction using Fortune's Algorithm
  •    COMP 163   
   

Welcome!

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.

Background

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.

The Sweepline

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.

The Beachline

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.

Events

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

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.

Circle Events

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.

DCEL

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.

Time Complexity

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).

Interactive Demo

Click anywhere on the canvas to begin adding points.

Please add five or more points before continuing.

Interactive Demo





   

References

  • Steven Fortune's paper "A Sweepline Algorithm for Voronoi Diargrams" in Algorithmica 1987.
  • Detailed discussion of the algorithm from the Georgia Tech CS 3510 course.
  • Visual explanation from the MIT 6.838 course.
  • Further details can be found on pages 158-167 of Computational Geometry: Algorithms and Applications 3E by Mark de Berg and others.
  • Video by Kevin Schaal demonstrating the algorithm as the sweepline continuously scans the point set.
  • Desmos graphing calculator showcasing the beachline behavior for a set of 5 points.
  • Javascript demo by Raymond Hill featuring a top-to-bottom sweep approach.

Credits

This demonstration is a project made for COMP 163, Fall 2017. It was made possible by the following components and libraries:

  • Twitter Bootstrap frontend framework.
  • D3.js interactive visualization library.
  • js-priority-queue fast priority queue implementation.
  • AlertifyJS modal dialog framework.

Thank you for your attention!