Scot listed about twenty fields in which Voronoi diagrams are in common use (although often not by that name).
In addition to all these "real world" applications, Voronoi diagrams have several applications within the field of computer science, in particular, computational geometry.
[A quick search through recent computational geometry literature finds
about 300 papers, almost all published in the last decade, with either
"Voronoi" or "Delaunay" in the title. Over a third of those papers
were published since 1990.]
Voronoi Diagrams -- Definitions and Examples
A Voronoi diagram of a set of "sites" (points) is a collection of regions that divide up the plane. Each region corresponds to one of the sites, and all the points in one region are closer to the corresponding site than to any other site.
All of the Voronoi regions are convex polygons. Some of them are infinite -- these correspond to the sites on the convex hull. The boundary between two adjacent regions is a line segment, and the line that contains it is the perpendicular bisector of the segment joining the two sites. Usually, Voronoi regions meet three at at time at Voronoi points. If three sites determine Voronoi regions that meet at a Voronoi point, the circle through those three sites is centered at that Voronoi point, and there are no other sites in the circle.
So how would this be useful for solving, say Knuth's Post Office Problem? Suppose we had the Voronoi diagram of the post office locations. Then the find the closest post office to a given house, all we need to do is figure out which Voronoi region the house is in. This is an example of the "point location" problem.
Once we have the Voronoi diagram, we can solve the post office problem as follows. (This is not the best solution, but it's reasonably simple.) Draw a vertical line through each of the Voronoi points. These lines split the plane into vertical slabs. To locate a point p, first do a binary search to find the slab containing p. Within each slab, there are no Voronoi points, so the Voronoi edges that cross each slab do so nicely. To find the Voronoi region containing p, we just do another binary search, this time on the spaces between the Voronoi edges in our slab. Altogether, the search takes O(log n) steps, where n is the number of sites.
Now let's look at the toxic waste dump problem. You are given n
points in the plane, representing cities, and you want to put a toxic
waste dump as far from the cities as possible. Obviously, the best
solution is to put the dump far away from ALL the points, but to make
the problem interesting, let's suppose we have to put the dump inside
the convex hull of the points. With this contraint, the best place to
put the waste dump is either (1) on a Voronoi vertex, or (2) on the
midpoint of a convex hull edge, which must be on a Voronoi edge.
The Delaunay triangulation is the dual of the Voronoi diagram. To build the Delaunay triangulation, draw a line segment between any two sites whose Voronoi regions share an edge. This procedure splits the convex hull of the sites into triangles.
The Delaunay triangulation has a number of nice properties. For example, each point is connected to its nearest neighbor by an edge in the triangulation. Since the Delaunay triangulation is a planar graph, it has at most 3n-6 edges, where n is the number of sites. So once you have the Dealunay triangulation, if you want to find the closest pair of sites, you only have to look at 3n-6 pairs, instead of all n(n-1)/2 possible pairs.
Here are some nice properties of the Delaunay triangulation:
One way of getting Voronoi diagrams is by growing crystals. If you start a number of crystals, all growing at the same rate, and all starting at the same time, you get a number of growing circles. As these circles meet, straight line boundaries appear between them. Eventually, the entire plane will be filled up. Each crystal will exactly fill up the Voronoi region of its point of origin.
This is a little too simple. In reality, crystals start growing at different times. Even if they still grow at the same rate, if they start at different times, they will no longer meet in straight lines. Instead, they will meet in hyperbolic segments. The diagram you get is called the "additively weighted Voronoi diagram". It's defined just like the usual Voronoi diagram, but each site has a weight, and you measure distance to a site, you add its weight to the usual Euclidean distance.
Now suppose instead that all the crystals start at the same time, but grow at different rates. Now you get what's called the "multiplicatively weighted Voronoi diagram". Once again, each site is given a weight, but when you measure the distance to a site, you multiply by its weight. Now the boundaries between different regions are segments of circles.
This model still has some problems. For example, in a multiplic- atively weighted Voronoi diagram, it's possible for a region to be disconnected. Obviously, this can't happen with real crystals. So there's yat another version which treats existing crystals as obstacles, and lets fast-growing crstals grow around the slower ones. Now the boundaries between neighboring regions are sort of tear-shaped. This variation is called the "multiplicatively weighted crystal growth Voronoi diagram."
There are several other variations. You can change the metric from the normal Euclidean distance to L1, or Lp, or Linfinity, or even stranger distance functions. You can weight the sites additively and mulitplicatively. You can change the sites from points to line segments or circles or polygons. You can generalize to higher dimensions. You can associate points with the farthest site, instead of their nearest site. And so on.
Different applications of Voronoi diagrams require different
variations. For example, motion planning algorithims for circular
robots often use the Voronoi diagram of the obstacles. If there is a
path from one location to another, then there must be a path that
follows the edges of the Voronoi diagram, since those edges are by
definition as far from the obstacles as possible.
Algorithms for Computing Voronoi Diagrams
There are literally hundreds of different algorithms for constructing various types of Voronoi diagrams. I will describe two of the simplest.
The first algorithm inserts the points one at a time into the diagram. Whenever a new point comes in, we need to do three things. First, we need to figure out which of the existing Voronoi cells contains the new site. Second, we need to "walk around" the boundary of the new site's Voronoi region, inserting new edges into the diagram. Finally, we delete all the old edges sticking into the new region.
The second and third steps are the harder ones. It's possible that
each new site's Voronoi cell will touch all the old cells. Thus, in
the worst case, we end up spending linear time on each cell, or
time overall. However, it has been proven that if you insert the
points in random order, the expected time is only O(n log n),
regardless of which set of points we're given.
A divide and conquer algorithm for constructing Voronoi diagrams was
discovered by Shamos and Hoey. Split the points into two halves, the
leftmost n/2 points, which we'll color bLue, and the rightmost n/2
points, which we'll color Red. Recursively compute the Voronio
diagram of the two halves. Finally, merge the two diagrams by finding
the edges that separate the bLue points from the Red points
The last step can be done in linear time by the "walking ant" method.
An ant starts down at -infinity, walking upward along the path halfway
between some blue point and some red point. The ant wants to walk all
the way up to +infinity, staying as far away from the points as
possible. Whenever the ant gets to a red Voronoi edge, it turns away
from the new red point. Whenever it hits a blue edge, it turns away
from the new blue point.
There are a few surprisingly difficult details left to deal with, like
how does the ant know where to start, and how do you know which edge
the ant will hit next. (The interested reader is strongly encouraged
to consult the standard computational geometry literature for
solutions to these details.)
References for Further Reading
Also suggested are a few of the standard computational geometry texts:
[Lightly formatted by DE from notes typed for geometry.forum by Jeff Erickson.]
Geometry in Action,
a collection of applications of computational geometry.
David Eppstein, Theory Group, ICS, UC Irvine.
Last update: 14 Nov 1996, 16:33:34 PST.