Geometry in Action

Scot Drysdale
Dartmouth College

Voronoi Diagrams: Applications from Archaology to Zoology

Regional Geometry Institute, Smith College
July 19, 1993
  1. Applications
  2. Definitions
  3. Delaunay Triangulations
  4. Variations
  5. Algorithms
  6. References

Applications of Voronoi Diagrams

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.

Delaunay Triangulations

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:

Variations on Voronoi Diagrams

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 O(n2) 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

  1. Okabe, Boots, and Sugihara, Spatial Tesselations: Concepts and Applications of Voronoi Diagrams, Wiley, 1992. This book describes everything mentioned in this talk, including an excellent survey of Voronoi applications in dozens of different fields.

  2. Aurenhammer, "Voronoi Diagrams: A Survey of a Fundamental Geometric Data Structure", ACM Computing Surveys 23 (1991), page 345-405. This is an excellent survey of recent technical results and a few applications, with several hundred references into the computational geometry literature.

    Also suggested are a few of the standard computational geometry texts:

  3. Preparata and Shamos, Computational Geometry: An Introduction, Springer-Verlag, 1985. Excellent introduction, at about the graduate student level, but somewhat out of date.

  4. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987. Much more thorough and technical than P&S. Not for the faint of heart. Again, slightly out of date.

  5. O'Rourke, Computational Geometry in C, to appear late this year. Joe's book will be a gentler (and more up-to-date) introduction than P&S, specifically designed for undergraduates.

[Lightly formatted by DE from notes typed for by Jeff Erickson.]

Part of Geometry in Action, a collection of applications of computational geometry.
David Eppstein, Theory Group, ICS, UC Irvine.

Last update: .