Voronoi diagram


In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. It can be classified also as a tessellation. In the simplest case, these objects are just finitely many points in the plane. For each seed there is a corresponding region, called a Voronoi cell, consisting of all points of the plane closer to that seed than to any other. The Voronoi diagram of a set of points is dual to that set's Delaunay triangulation.
The Voronoi diagram is named after mathematician Georgy Voronoy, and is also called a Voronoi tessellation, a Voronoi decomposition, a Voronoi partition, or a Dirichlet tessellation. Voronoi cells are also known as Thiessen polygons, after Alfred H. Thiessen. Voronoi diagrams have practical and theoretical applications in many fields, mainly in science and technology, but also in visual art.

Simplest case

In the simplest case, shown in the first picture, we are given a finite set of points in the Euclidean plane. In this case, each point has a corresponding cell consisting of the points in the Euclidean plane for which is the nearest site: the distance to is less than or equal to the minimum distance to any other site. For one other site, the points that are closer to than to, or equally distant, form a closed half-space, whose boundary is the perpendicular bisector of line segment. Cell is the intersection of all of these half-spaces, and hence it is a convex polygon. When two cells in the Voronoi diagram share a boundary, it is a line segment, ray, or line, consisting of all the points in the plane that are equidistant to their two nearest sites. The vertices of the diagram, where three or more of these boundaries meet, are the points that have three or more equally distant nearest sites.

Formal definition

Let be a metric space with distance function. Let be a set of indices and let be a tuple of nonempty subsets in the space. The Voronoi cell, or Voronoi region, , associated with the site is the set of all points in whose distance to is not greater than their distance to the other sites, where is any index different from. In other words, if denotes the distance between the point and the subset, then
The Voronoi diagram is simply the tuple of cells. In principle, some of the sites can intersect and even coincide, but usually they are assumed to be disjoint. In addition, infinitely many sites are allowed in the definition, but again, in many cases only finitely many sites are considered.
In the particular case where the space is a finite-dimensional Euclidean space, each site is a point, there are finitely many points and all of them are different, then the Voronoi cells are convex polytopes and they can be represented in a combinatorial way using their vertices, sides, two-dimensional faces, etc. Sometimes the induced combinatorial structure is referred to as the Voronoi diagram. In general however, the Voronoi cells may not be convex or even connected.
In the usual Euclidean space, we can rewrite the formal definition in usual terms. Each Voronoi polygon is associated with a generator point .
Let be the set of all points in the Euclidean space. Let be a point that generates its Voronoi region , that generates , and that generates , and so on. Then, as expressed by Tran et al, "all locations in the Voronoi polygon are closer to the generator point of that polygon than any other generator point in the Voronoi diagram in Euclidean plane".

Illustration

As a simple illustration, consider a group of shops in a city. Suppose we want to estimate the number of customers of a given shop. With all else being equal, it is reasonable to assume that customers choose their preferred shop simply by distance considerations: they will go to the shop located nearest to them. In this case the Voronoi cell of a given shop can be used for giving a rough estimate on the number of potential customers going to this shop.
For most cities, the distance between points can be measured using the familiar
Euclidean distance:
or the Manhattan distance:
The corresponding Voronoi diagrams look different for different distance metrics.

Properties

  • The dual graph for a Voronoi diagram corresponds to the Delaunay triangulation for the same set of points.
  • The closest pair of points corresponds to two adjacent cells in the Voronoi diagram.
  • If the setting is the Euclidean plane and a discrete set of points is given, then two points of the set are adjacent on the convex hull if and only if their Voronoi cells share an infinitely long side.
  • If the space is a normed space and the distance to each site is attained, then each Voronoi cell can be represented as a union of line segments emanating from the sites. As shown there, this property does not necessarily hold when the distance is not attained.
  • Under relatively general conditions Voronoi cells enjoy a certain stability property: a small change in the shapes of the sites, e.g., a change caused by some translation or distortion, yields a small change in the shape of the Voronoi cells. This is the geometric stability of Voronoi diagrams. As shown there, this property does not hold in general, even if the space is two-dimensional and the sites are points.

    History and research

Informal use of Voronoi diagrams can be traced back to Descartes in 1644. Peter Gustav Lejeune Dirichlet used two-dimensional and three-dimensional Voronoi diagrams in his study of quadratic forms in 1850.
British physician John Snow used a Voronoi-like diagram in 1854 to illustrate how the majority of people who died in the Broad Street cholera outbreak lived closer to the infected Broad Street pump than to any other water pump.
Voronoi diagrams are named after Georgy Feodosievych 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 are called Thiessen polygons after American meteorologist Alfred H. Thiessen, who used them to estimate rainfall from scattered measurements in 1911. Other equivalent names for this concept : Voronoi polyhedra, Voronoi polygons, domain of influence, Voronoi decomposition, Voronoi tessellation, Dirichlet tessellation.

Examples

Voronoi tessellations of regular lattices of points in two or three dimensions give rise to many familiar tessellations.
Certain body-centered tetragonal lattices give a tessellation of space with rhombo-hexagonal dodecahedra.
For the set of points 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 nth-order Voronoi diagram from set S, start with the th-order diagram and replace each cell generated by X = with a Voronoi diagram generated on the set S − X.

Farthest-point Voronoi diagram

For a set of n points, the th-order Voronoi diagram is called a farthest-point Voronoi diagram.
For a given set of points S = , the farthest-point Voronoi diagram divides the plane into cells in which the same point of P is the farthest point. A point of P has a cell in the farthest-point Voronoi diagram if and only if it is a vertex of the convex hull of P. Let H = be the convex hull of P; then the farthest-point Voronoi diagram is a subdivision of the plane into k cells, one for each point in H, with the property that a point q lies in the cell corresponding to a site hi if and only if d > d for each pj ∈ S with hi ≠ pj, where d is the Euclidean distance between two points p and q.
The boundaries of the cells in the farthest-point Voronoi diagram have the structure of a topological tree, with infinite rays as its leaves. Every finite tree is isomorphic to the tree formed in this way from a farthest-point Voronoi diagram.

Generalizations and variations

As implied by the definition, Voronoi cells can be defined for metrics other than Euclidean, such as the Mahalanobis distance or Manhattan distance. However, in these cases the boundaries of the Voronoi cells may be more complicated than in the Euclidean case, since the equidistant locus for two points may fail to be subspace of codimension 1, even in the two-dimensional case.
Image:Approximate Voronoi Diagram.svg|thumb|Approximate Voronoi diagram of a set of points. Notice the blended colors in the fuzzy boundary of the Voronoi cells.
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. In contrast to the case of Voronoi cells defined using a distance which is a metric, in this case some of the Voronoi cells may be empty. A power diagram is a type of Voronoi diagram defined from a set of circles using the power distance; it can also be thought of as a weighted Voronoi diagram in which a weight defined from the radius of each circle is added to the squared Euclidean distance from the circle's center.
The Voronoi diagram of points in -dimensional space can have vertices, requiring the same bound for the amount of memory needed to store an explicit description of it. Therefore, Voronoi diagrams are often not feasible for moderate or high dimensions. A more space-efficient alternative is to use approximate Voronoi diagrams.
Voronoi diagrams are also related to other geometric structures such as the medial axis, straight skeleton, and zone diagrams.