Voronoi Diagrams and Delaunay Triangulations

01 January 1997

New Image

The Voronoi diagram of a set of sites partitions space into regions, one per site; the region for a site s consists of all points closer to s than to any other site. The dual of the Voronoi diagram, the Delaunay triangulation, is the unique triangulation such that the circumsphere of every simplex contains no sites in its interior. Voronoi diagrams and Delaunay triangulations have been rediscovered or applied in many areas of mathematics and the natural sciences; they are central topics in computational geometry, with hundreds of papers discussing algorithms and extensions. Section 20.1 discusses the definition and basic properties in the usual case of point sites in R sup d with the Euclidean metric, while Section 20.2 gives basic algorithms. Some of the many extensions obtained by varying metric, sites, environment, and constraints are discussed in Section 20.3. Section 20.4 finishes with some interesting and nonobvious structural properties of Voronoi diagrams and Delaunay triangulations.