Input description: A set S of points .
Problem description: Decompose space into regions around each point such that all the points in the region around are closer to than they are to any other point in S.
Discussion: Voronoi diagrams represent the region of influence around each of a given set of sites. If these sites represent the locations of McDonald's restaurants, the Voronoi diagram partitions space into cells around each restaurant. For each person living in a particular cell, the defining McDonald's represents the closest place to get a Big Mac.
Voronoi diagrams have a surprising variety of uses:
Each edge of a Voronoi diagram is part of the perpendicular bisector of two points in S, since this is the line that partitions the plane between the points. The conceptually simplest method to construct Voronoi diagrams is randomized incremental construction. To add another site to the diagram, locate the cell that contains it and add the perpendicular bisectors between the new site and all sites defining impacted regions. When the sites are inserted in random order, only a small number of regions are likely to be impacted.
However, the method of choice is Fortune's sweepline algorithm, especially since robust implementations of it are readily available. Use an existing implementation instead of trying to develop your own. The algorithm works by projecting the set of sites in the plane into a set of cones in three dimensions such that the Voronoi diagram is defined by projecting the cones back onto the plane. The advantages of Fortune's algorithm are (1) it runs in optimal time, (2) it is reasonable to implement, and (3) we need not store the entire diagram if we can use it as we sweep over it.
There is an interesting relationship between convex hulls in d+1 dimensions and Delaunay triangulations (or equivalently Vornoi diagrams) in d-dimensions, which provides the best way to construct Voronoi diagrams in higher dimensions. By projecting each site in into the point , taking the convex hull of this (d+1)-dimensional point set and then projecting back into d dimensions we obtain the Delaunay triangulation. Details are given in the references below. Programs that compute higher-dimensional convex hulls are discussed in Section .
Several important variations of standard Voronoi diagrams arise in practice. See the references below for details:
Implementations: Steve Fortune is the author of a widely used 2D code for Voronoi diagrams and Delaunay triangulations, written in C. It is based on his own sweepline algorithm [For87] for Voronoi diagrams and is likely to be the right code to try first. It is available from Netlib (see Section ) at http://netlib.bell-labs.com/netlib/voronoi/index.html.
LEDA (see Section ) provides an implementation of a randomized incremental construction algorithm for planar Voronoi diagrams in C++.
Higher-dimensional and furthest-site Voronoi diagrams can be constructed as a special case of higher-dimensional convex hulls. Qhull [BDH97] appears to be the convex hull code of choice in three dimensions and beyond. It is written in C, and it can also construct Delaunay triangulations and half-space intersections. Qhull has been widely used in scientific applications and has a well-maintained home page at http://www.geom.umn.edu/software/qhull/.
The Stanford GraphBase (see Section ) contains an implementation of a randomized incremental algorithm to construct Voronoi diagrams and Delaunay triangulations for use as a generator of planar graph instances.
Algorithm 558 [Che80] of the Collected Algorithms of the ACM is a Fortran code for the multifacility location problem. It is based on a network flow approach, instead of using Voronoi diagrams. Interestingly, the network flow code is taken from Nijenhuis and Wilf (see Section ). See Section .
Notes: Voronoi diagrams were studied by Dirichlet in 1850 and are occasionally referred to as Dirichlet tessellations. They are named after G. Voronoi, who discussed them in a 1908 paper. In mathematics, concepts get named after the last person to discover them.
Aurenhammer [Aur91] and Fortune [For92] provide excellent surveys on Voronoi diagrams and associated variants such as power diagrams. The first algorithm for constructing Voronoi diagrams was based on divide-and-conquer and is due to Shamos and Hoey [SH75]. Good expositions of Fortune's sweepline algorithm for constructing Voronoi diagrams in [For87] include [O'R94]. Good expositions on the relationship between Delaunay triangulations and (d+1)-dimensional convex hulls [ES86] include [O'R94].
In a kth-order Voronoi diagram, we partition the plane such that each point in a region is closest to the same set of k sites. Using the algorithm of [ES86], the complete set of kth-order Voronoi diagrams can be constructed in time. By doing point location on this structure, the k nearest neighbors to a query point can be found in . Expositions on kth-order Voronoi diagrams include [O'R94, PS85].
The smallest enclosing circle problem can be solved in time using (n-1)st order Voronoi diagrams [PS85]. In fact, there exist linear-time algorithms based on low-dimensional linear programming [Meg83]. A linear algorithm for computing the Voronoi diagram of a convex polygon is given by [AGSS89].
Related Problems: Nearest neighbor search (see page ), point location (see page ), triangulation (see page ).