Voronoi diagrams

F. Aurenhammer and R. Klein

Abstract:

The topic of this chapter - Voronoi diagrams - differs from other areas of computational geometry, in that its origin dates back to the 17th century. In his book on the principles of philosophy, R. Descartes' illustrations show a decomposition of space into convex regions, whose underlying idea seems to be that of a Voronoi diagram. This concept has independently emerged, and proven useful, in various fields of science. Different names particular to the respective field have been used, such as medial axis transform in biology and physiology, Wigner-Seitz zones in chemistry and physics, domains of action in crystallography, and Thiessen polygons in metereology and geography. The mathematicians Dirichlet and Voronoi were the first to formally introduce this concept. The resulting structure has been called Dirichlet tessellation or Voronoi diagram, which has become its standard name today. Voronoi was the first to consider the dual of this structure, where any two point sites are connected whose regions have a boundary in common. Later, Delaunay obtained the same by defining that two point sites are connected if and only if they lie on a circle whose interior contains no other point site. After him, the dual of the Voronoi diagram has been denoted Delaunay tessellation or Delaunay triangulation. Besides its applications in other fields of science, the Voronoi diagram and its dual can be used for solving numerous, and surprisingly different, geometric problems. Moreover, these structures are very appealing, and a lot of research has been devoted to their study (about one out of 16 papers in computational geometry), ever since Shamos and Hoey introduced them to the field. Within one chapter, we cannot review all known results and applications. Instead, we are trying to highlight the intrinsic potential of Voronoi diagrams, that lies in its structural properties, in the existence of efficient algorithms for its construction, and in its adaptability.

Reference: F. Aurenhammer and R. Klein. Voronoi diagrams. In J. Sack and G. Urrutia, editors, Handbook of Computational Geometry, Chapter V, pages 201-290. Elsevier Science Publishing, 2000. [SFB Report F003-092, TU Graz, Austria, 1996].