Voronoi diagram

The Voronoi diagram of a random set of points in the plane (all points lie within the image).

In mathematics, a Voronoi diagram is a 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. It is named after Georgy Voronoi, also called a Voronoi tessellation, a Voronoi decomposition, a Dirichlet tessellation (after Lejeune Dirichlet), or a Thiessen Polygon.

In the simplest case, we are given a set of points S in the plane, which are the Voronoi sites. Each site s has a Voronoi cell, also called a Dirichlet cell, V(s) consisting of all points closer to s than to any other site. The segments of the Voronoi diagram are all the points in the plane that are equidistant to the two nearest sites. The Voronoi nodes are the points equidistant to three (or more) sites.

Definition

Let S be a set of points in Euclidean space with all limit points contained in S. For almost any point x in the Euclidean space, there is one point of S closest to x. The word "almost" is used to indicate exceptions where 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.

Properties

• The dual graph for a Voronoi diagram corresponds to the Delaunay triangulation for the same set of points S.
• The closest pair of points corresponds to two adjacent cells in the Voronoi diagram.
• Two points are adjacent on the convex hull if and only if their Voronoi cells share an infinitely long side.

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. 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.

Examples

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 tessellation is not a 2D Voronoi tessellation 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' centers 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

For 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.

Higher-order Voronoi diagrams

Although a normal Voronoi cell is defined as the set of points closest to a single point in S, an nth-order Voronoi cell is defined as the set of points having a particular set of n points in S as its n nearest neighbors. Higher-order Voronoi diagrams also subdivide space.

Higher-order Voronoi diagrams can be generated recursively. To generate the n^th-order Voronoi diagram from set S, start with the (n − 1)^th-order diagram and replace each cell generated by X = {x₁, x₂, ..., x_n−1} with a Voronoi diagram generated on the set S − X.

Generalizations

Voronoi cells can be defined for metrics other than Euclidean (such as the Mahalanobis or Manhattan) distances. 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 objects that are not points. The Voronoi diagram with these cells is also called the medial axis. Even when the objects are line segments, the Voronoi cells are not bounded by straight lines. The medial axis is 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. A simplified version of the Voronoi diagram of line segments is the straight skeleton.

A weighted Voronoi diagram is the one in which the function of a pair of points to define a Voronoi cell is a distance function modified by multiplicative or additive weights assigned to generator points.

Approximate Voronoi diagram of a set of points. Notice the blended colors in the fuzzy boundary of the Voronoi cells.

The Voronoi diagram of n points in d-dimensional space requires $O(n^{\lceil d/2 \rceil})$ storage space. Therefore, Voronoi diagrams are often not feasible for d > 2. An alternative is to use approximate Voronoi diagrams, where the Voronoi cells have a fuzzy boundary, which can be approximated.

Applications

A point location data structure can be built on top of the Voronoi diagram in order to answer nearest neighbor queries, where one wants to find the object that is closest to a given query point. Nearest neighbor queries have numerous applications. For example, when one wants to find the nearest hospital, or the most similar object in a database. A large application is vector quantization, commonly used in data compression.

With a given Voronoi diagram, one can also find the largest empty circle amongst a set of points, and in an enclosing polygon; e.g. to build a new supermarket as far as possible from all the existing ones, lying in a certain city.

The Voronoi diagram is useful in polymer physics. It can be used to represent free volume of the polymer.

It is also used in derivations of the capacity of a wireless network.

In climatology, Voronoi diagrams are used to calculate the rainfall of an area, based on a series of point measurements. In this usage, they are generally referred to as Thiessen polygons.

Voronoi diagrams are used to study the growth patterns of forests and forest canopies, and may also be helpful in developing predictive models for forest fires.

Voronoi diagrams are also used in computer graphics to procedurally generate some kinds of organic looking textures.

In autonomous robot navigation, Voronoi diagrams are used to find clear routes. If the points are obstacles, then the edges of the graph will be the routes furthest from obstacles (and theoretically any collisions).

In computational chemistry, Voronoi cells defined by the positions of the nuclei in a molecule are used to compute atomic charges. This is done using the Voronoi deformation density method.

See also

Algorithms

• Bowyer-Watson algorithm -- an algorithm for generating a Voronoi diagram in any number of dimensions.
• Fortune's algorithm -- an O(n log(n)) algorithm for generating a Voronoi diagram from a set of points in a plane.
• Lloyd's algorithm

Related subjects

• Centroidal Voronoi tessellation
• Computational geometry
• Delaunay triangulation
• Mathematical diagram
• Nearest neighbor search
• Nearest-neighbor interpolation

References

• 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 0-471-98635-6
• Franz Aurenhammer (1991). Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure. ACM Computing Surveys, 23(3):345-405, 1991.
• Adrian Bowyer (1981). Computing Dirichlet tessellations, The Computer Journal 1981 24(2):162-166.
• David F. Watson (1981). Computing the n-dimensional tessellation with application to Voronoi polytopes, The Computer Journal, Heyden & Sons Ltd., Vol 2, Num 24, pp.167-172.
• Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000). Computational Geometry (2nd revised edition ed.). Springer-Verlag. ISBN 3-540-65620-0.  Chapter 7: Voronoi Diagrams: pp. 147–163. Includes a description of Fortune's algorithm.
• Farid Karimipour, Mehran Ghandehari, and Hugo Ledoux (2013). 'Watershed Delineation from the Medial Axis of River Networks', Journal of Computers & Geosciences, Vol. 59, No. 3, pp. 132-147.https://dl.dropboxusercontent.com/u/88424941/Article/journal/C%26G_MehranGhandehari.pdf
• Farid Karimipour and Mehran Ghandehari (2013). 'Voronoi-based Medial Axis Approximation from Samples: Issues and Solutions', Transactions on Computational Sciences Journal, Springer.https://dl.dropboxusercontent.com/u/88424941/Article/Book%20Chapter/ICCSA2012_MehranGhandehari.pdf
• Farid Karimipour and Mehran Ghandehari (2012). 'A Stable Voronoi-based Algorithm for Medial Axis Extraction through Labeling Sample Points', IEEE Proceedings of the 9th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2012), New Jersey, USA, June 27-29, 2012, pp. 115-123.https://dl.dropboxusercontent.com/u/88424941/Article/Conference/ISVD2012_MehranGhandehari.pdf

External links

• Real time interactive Voronoi and Delaunay diagrams with source code
• Real time interactive Voronoi diagram applet
• Demo for various metrics
• Mathworld on Voronoi diagrams
• Qhull for computing the Voronoi diagram in 2-d, 3-d, etc.
• Voronoi Diagrams: Applications from Archaeology to Zoology
• Voronoi Diagrams in CGAL, the Computational Geometry Algorithms Library
• Voronoi Web Site : using Voronoi diagrams for spatial analysis
• More discussions and picture gallery on centroidal Voronoi tessellations
• Lloyd's method for creating a centroidal Voronoi diagram from an original set of generating points
• Voronoi Diagrams in Python
• Voronoi Diagram Research Center
• Constructing 3D Models from Voronoi Diagrams
• Voronoi/Voronoy Tessellation
• Voronoi Diagrams by Ed Pegg, Jr., Jeff Bryant, and Theodore Gray, Wolfram Demonstrations Project.