Voronoi diagram
|
|
In mathematics, a Voronoi diagram, also called a Voronoi tessellation or Voronoi decomposition, named after Georgy Voronoi, also called a Dirichlet tessellation, after Lejeune Dirichlet, is special kind of decomposition of a metric space determined by distances to a specified discrete set of objects in the space, e.g., by a discrete set of points.
| Contents |
Definition
For any (topologically) discrete set S of points in Euclidean space and for almost any point x, there is one point of S to which x is closer than x is to any other point of S. The word "almost" is occasioned by the fact that a point x may be equally close to two or more points of S.
If S contains only two points, a, and b, then the set of all points equidistant from a and b is a hyperplane --- an affine subspace of codimension 1. That hyperplane is the boundary between the set of all points closer to a than to b, and the set of all points closer to b than to a.
In general, the set of all points closer to a point c of S than to any other point of S is the interior of a (in some cases unbounded) convex polytope called the Dirichlet domain or Voronoi cell for c. The set of such polytopes tesselates the whole space, and is the Voronoi tessellation corresponding to the set S. If the dimension of the space is only 2, then it is easy to draw pictures of Voronoi tessellations, and in that case they are sometimes called Voronoi diagrams.
The dual for a Voronoi tessellation is the Delaunay triangulation for the same set of points S.
History
Informal use of Voronoi diagrams can be traced back to Descartes in 1644. Dirichlet used 2-dimensional and 3-dimensional Voronoi diagrams in his study of quadratic forms in 1850. British physician John Snow used a Voronoi diagram in 1854 to illustrate how the majority of people who died in the Soho cholera epidemic lived closer to the infected Broad Street pump than to any other water pump.
Voronoi diagrams are named after Russian mathematician Georgy Fedoseevich Voronoi (or Voronoy) who defined and studied the general n-dimensional case in 1908. Voronoi diagrams that are used in geophysics and meteorology to analyse spatially distributed data (such as rainfall measurements) are called Thiessen polygons after American meteorologist Alfred H. Thiessen. In condensed matter physics, such tessellations are also known as "Wigner-Seitz unit cells". Voronoi tessellations of the reciprocal lattice of momenta are called Brillouin zones.
Examples
Voronoi tessellations of regular lattices of points in two or three dimensions give rise to many familiar tessellations.
- A square lattice gives the usual tessellation of squares.
- A triangular lattice gives the honeycomb tessellation of hexagons
- A pair of planes with triangular lattices aligned with each others' centres gives the arrangement of rhombus-capped hexagonal prisms seen in honeycomb
- A face-centred cubic lattice gives a tessellation of space with rhombic dodecahedra
- A body-centred cubic lattice gives a tessellation of space with truncated octahedra
Generalizations
Voronoi cells can be defined for metrics other than Euclidean. However in these cases the Voronoi tessellation is not guaranteed to exist (or to be a "true" tessellation), since the equidistant locus for two points may fail to be subspace of codimension 1, even in the 2-dimensional case.
Voronoi cells can also be defined by measuring distances to areas rather than to points. These types of Voronoi cells are used in image segmentation, optical character recognition and other computational applications.
References
- Georgy Voronoi (1908). Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Journal fur die Reine und Angewandte Mathematik, 133:97-178, 1908
- Atsuyuki Okabe, Barry Boots, Kokichi Sugihara & Sung Nok Chiu (2000). Spatial Tessellations - Concepts and Applications of Voronoi Diagrams. 2nd edition. John Wiley, 2000, 671 pages ISBN 0471986356
- Franz Aurenhammer (1991). Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure. ACM Computing Surveys, 23(3):345-405, 1991.
External links
- Voronoi Web Site : using Voronoi diagrams for spatial analysis (http://www.voronoi.com/)
- Voronoi Diagrams: Applications from Archaeology to Zoology (http://www.ics.uci.edu/~eppstein/gina/scot.drysdale.html)de:Voronoi-Diagramm