Voronoi Diagrams

  

 

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:

• Nearest neighbor search - For a query point q, finding its nearest neighbor from a fixed set of points S is simply a matter of determining which cell in the Voronoi diagram of S contains q. See Section for more details.  
• Facility location - Suppose McDonald's wanted to open another restaurant. To minimize interference with existing McDonald's, it should be located as far away from the closest restaurant as possible. This location is always at a vertex of the Voronoi diagram, and it can be found in a linear-time search through all the Voronoi vertices.  
• Largest empty circle - Suppose you needed to obtain a large, contiguous, undeveloped piece of land on which to build a factory. The same condition used for picking McDonald's locations is appropriate for other undesirable facilities, namely that it be as far as possible from any relevant sites of interest. A Voronoi vertex defines the center of the largest empty circle among the points.   
• Path planning - If the sites of S are the centers of obstacles we seek to avoid, the edges of the Voronoi diagram define the possible channels that maximize the distance to the obstacles. Thus in planning paths among the sites, it will be ``safest'' to stick to the edges of the Voronoi diagram.   
• Quality triangulations - In triangulating a set of points, we often desire nice, fat triangles, which avoid small angles and skinny triangles. The Delaunay triangulation maximizes the minimum angle over all triangulations and is exactly what we want. Further, it is easily constructed as the dual of the Voronoi diagram. See Section for details.     

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:

• Non-Euclidean distance metrics - Recall that the idea of a Voronoi diagram is to decompose space into regions of influence around each of the given sites. Thus far, we have assumed that Euclidean distance measures influence, but for many applications this is inappropriate. If people drive to McDonald's, the time it takes to get there depends upon where the major roads are. Efficient algorithms are known for constructing Voronoi diagrams under a variety of different metrics, and for curved or constrained objects.  
• Power diagrams - These structures decompose space into regions of influence around the sites, where the sites are no longer constrained to have all the same power. Imagine a map of the listening range of a set of radio stations operating at a given frequency. The region of influence around a station depends both on the power of its transmitter and the position of neighboring transmitters.    
• kth-order and furthest-site diagrams - The idea of decomposing space into regions sharing some property can be taken beyond closest-point Voronoi diagrams. Any point within a single cell of the kth-order Voronoi diagram shares the same set of k closest points in S. In furthest-site diagrams, any point within a particular region shares the same furthest point in S. Point location (see Section ) on these structures permits fast retrieval of the appropriate points.   

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