F. Aurenhammer and R. Klein
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.
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].