Voronoi diagram
 |
This is the Voronoi diagram of a random set of points in the plane (all points lie within the image). |
In
mathematics, a
Voronoi diagram, named after
Georgy Voronoi, also called a
Voronoi tessellation, a
Voronoi decomposition, or 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.
For any (
topologically) discrete set
S of points in
Euclidean space and for almost any point
x, there is one point of
S closest to
x. 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. It is the perpendicular
bisector of the line segment from
a and
b.
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
tessellates 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.
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. For general lattices in
Lie groups, the cells are simply called
fundamental domains. In the case of general
metric spaces, the cells are often called metric
fundamental polygons.
 |
This is a slice of the Voronoi diagram of a random set of points in a 3D box. In general a cross section of a 3D Voronoi tesselation is not a 2D Voronoi tesselation itself. (The cells are all convex polyhedra.) |
Voronoi tessellations of regular
lattices of points in two or three dimensions give rise to many familiar tessellations.
* A 2D lattice gives an irregular
honeycomb tessellation, with equal
hexagons with point symmetry; in the case of a regular triangular lattice it is regular; in the case of a rectangular lattice the hexagons reduce to rectangles in rows and columns; a
square lattice gives the regular tessellation of squares.
* 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 octahedraFor the set of points (
x,
y) with
x in a discrete set
X and
y in a discrete set
Y, we get rectangular tiles with the points not necessarily at their centers.
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. In materials science, polycrystalline microstructures in metallic alloys are commonly represented using Voronoi tessellations.
*
Gustav Lejeune Dirichlet (1850).
Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen. Journal für die Reine und Angewandte Mathematik,
40:209-227.
* Georgy Voronoi (1907).
Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Journal für die Reine und Angewandte Mathematik,
133:97-178, 1907
* 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.
*
Applet for calculation and visualization of convex hull, Delaunay triangulations and Voronoi diagrams in space*
Voronoi Web Site : using Voronoi diagrams for spatial analysis*
Voronoi Diagrams: Applications from Archaeology to Zoology*
Demo for various metrics*
Parameterized and programmed architectural object using the Voronoi Diagram*
VoronoiDiagramAdaptor2
