The Voronoi Diagram of n sites is a subdivision of the plane into n regions, one per site. Each site's region consists of all points in the plane closer to that site than to any of the other n-1 sites.
It is amazing how useful this simply described diagram is. The Voronoi Diagram and its geometric dual, the Delaunay Triangulation, have proved to be two of the most important data structures in Computational Geometry. The Voronoi Diagram and its variants (different metrics, higher dimensions, sites which are segments or polygons instead of points, etc.) have been rediscovered many times in literally dozens of fields, including biology, crystallography, geology, metallurgy, mesh generation, curve and surface reconstruction, meteorology, mathematics, robotics, geography, and marketing. A book-length survey of the types of Voronoi Diagrams and their applications in a variety of fields was written by Okabe, Boots, and Sugihara [1].
Voronoi diagrams and their applications are an active field of research. In recent years between 3 and 6 of the approximately 40 papers accepted to the annual Symposium on Computational Geometry have been on Voronoi diagrams or their applications.
One of the applications that is the subject of a flurry of recent papers is a group of algorithms for curve and surface reconstruction ([2] is the paper that started the recent activity in this area and [3] is one of the most recent papers on the subject). The algorithms take a sample of points from a curve in 2-D or a surface in 3-D (perhaps from a medical image or a machine that records 3-D points in space) and construct a representation of the curve or surface sampled.
Another important application of Voronoi diagrams that is still an active area of research is mesh generation ([4],[5],[6]). However, not all recent work is applied. Researchers are still exploring fundamental properties of these diagrams ([7]) and new variations on the diagram ([8]).
We will look at the properties of Voronoi diagrams that make them so widely applicable, discuss the advantages and drawbacks to the various algorithms for computing them, and will look at a number of specific applications, including the surface reconstruction algorithm discussed above.
Much of the material covered can be incorporated into undergraduate algorithms courses. The Voronoi diagram (or Delaunay Triangulation) can be constructed via a number of approaches: iterative algorithms, divide-and-conquer, and sweepline methods are among the approaches used. This variety of approaches leads to interesting questions in both theoretical and experimental analysis of algorithms. The topic can also be a large component of a topics course devoted to Computational Geometry. The text by O'Rourke [9] is designed for such an undergraduate course.
The properties of the diagram provide an interesting test bed for showing the usefulness of mathematical proofs and give students practice in constructing proofs. The properties are non-trivial and sometimes surprising, but none requires a level of mathematical understanding beyond that gained in high school geometry. Thus they are both challenging and accessible to undergraduate students.
The wide variety of applications and concrete visual representation of
the diagram make it a good example for undergraduate courses.
Prerequisites: Participants should have a solid grounding in data
structures and algorithms. If in doubt, apply.
References: