This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate? Excessive Violence Sexual Content Political / Social
Email Address:
Article Id: WHEBN0000177668 Reproduction Date:
In mathematics, a Voronoi diagram is a partitioning of a plane into regions based on distance to points in a specific subset of the plane. That set of points (called seeds, sites, or generators) is specified beforehand, and for each seed there is a corresponding region consisting of all points closer to that seed than to any other. These regions are called Voronoi cells. The Voronoi diagram of a set of points is dual to its Delaunay triangulation. Put simply, it's a diagram created by taking pairs of points that are close together and drawing a line that is equidistant between them and perpendicular to the line connecting them. That is, all points on the lines in the diagram are equidistant to the nearest two (or more) source points.
It is named after tessellation, a Voronoi decomposition, a Voronoi partition, or a Dirichlet tessellation (after Peter Gustav Lejeune Dirichlet). Voronoi diagrams have practical and theoretical applications to a large number of fields, mainly in science and technology but also including visual art.^{[1]}^{[2]}
In the simplest and most familiar case (shown in the first picture), we are given a finite set of points {p_{1}, …, p_{n}} in the Euclidean plane. In this case each site p_{k} is simply a point, and its corresponding Voronoi cell (also called Voronoi region or Dirichlet cell) R_{k} consists of every point whose distance to p_{k} is less than or equal to its distance to any other p_{k}. Each such cell is obtained from the intersection of half-spaces, and hence it is a convex polygon. The segments of the Voronoi diagram are all the points in the plane that are equidistant to the two nearest sites. The Voronoi vertices (nodes) are the points equidistant to three (or more) sites.
Let \scriptstyle X be a metric space with distance function \scriptstyle d. Let \scriptstyle K be a set of indices and let \scriptstyle (P_k)_{k \in K} be a tuple (ordered collection) of nonempty subsets (the sites) in the space \scriptstyle X. The Voronoi cell, or Voronoi region, \scriptstyle R_k, associated with the site \scriptstyle P_k is the set of all points in \scriptstyle X whose distance to \scriptstyle P_k is not greater than their distance to the other sites \scriptstyle P_j, where \scriptstyle j is any index different from \scriptstyle k. In other words, if \scriptstyle d(x,\, A) \;=\; \inf\{d(x,\, a) \mid a \,\in\, A\} denotes the distance between the point \scriptstyle x and the subset \scriptstyle A, then
The Voronoi diagram is simply the tuple of cells \scriptstyle (R_k)_{k \in K} . In principle some of the sites can intersect and even coincide (an application is described below for sites representing shops), but usually they are assumed to be disjoint. In addition, infinitely many sites are allowed in the definition (this setting has applications in geometry of numbers and crystallography), 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, 2-dimensional faces, etc. Sometimes the induced combinatorial structure is referred to as the Voronoi diagram. However, in general 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 \scriptstyle R_k is associated with a generator point \scriptstyle P_k. Let \scriptstyle X the set of all points in the Euclidean space. Let \scriptstyle P_1 be a point that generates its Voronoi region \scriptstyle R_1, \scriptstyle P_2 that generates \scriptstyle R_2, and \scriptstyle P_3 that generates \scriptstyle R_3, and so on. Then, as expressed by Tran et al^{[3]} "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 Euclidian plane".
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 (price, products, quality of service, etc.), 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 \scriptstyle R_k of a given shop \scriptstyle P_k can be used for giving a rough estimate on the number of potential customers going to this shop (which is modeled by a point in our city).
For most cities, the distance between points can be measured using the familiar Euclidean distance: \ell_2 = d\left[\left(a_1, a_2\right), \left(b_1, b_2\right)\right] = \sqrt{\left(a_1 - b_1\right)^2 + \left(a_2 - b_2\right)^2} or the Manhattan distance:d\left[\left(a_1, a_2\right), \left(b_1, b_2\right)\right] = \left|a_1 - b_1\right| + \left|a_2 - b_2\right|. The corresponding Voronoi diagrams look different for different distance metrics.
Informal use of Voronoi diagrams can be traced back to Descartes in 1644. Peter Gustav Lejeune 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 and Ukrainian mathematician 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. Other equivalent names for this concept (or particular important cases of it): Voronoi polyhedra, Voronoi polygons, domain(s) of influence, Voronoi decomposition, Voronoi tessellation(s), Dirichlet tessellation(s).
Voronoi tessellations of regular lattices of points in two or three dimensions give rise to many familiar tessellations.
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.
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_{1}, x_{2}, ..., x_{n−1}} with a Voronoi diagram generated on the set S − X.
For a set of n points the (n − 1)^{th}-order Voronoi diagram is called a farthest-point Voronoi diagram.
For a given set of points S = {p_{1}, p_{2}, ..., p_{n}} the farthest-point Voronoi diagram divides the plane into cells in which the same point of P is the farthest point. Note that 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. Thus, let H = {h_{1}, h_{2}, ..., h_{k}} be the convex hull of P we define the farthest-point Voronoi diagram as the 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 h_{i} if and only if dist(q, h_{i}) > dist(q, p_{j}) for each p_{j} ∈ S with h_{i} ≠ p_{j}. Where dist(p, q) is the Euclidean distance between two points p and q.^{[6]}^{[7]}
As implied by the definition, Voronoi cells can be defined for metrics other than Euclidean (such as the Mahalanobis or Manhattan) distances. 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 2-dimensional case.
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 distance from the circle's center.^{[8]}
The Voronoi diagram of n points in d-dimensional space requires \scriptstyle O\left(n^{\left\lceil \frac{1}{2}d \right\rceil}\right) 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.^{[9]} Another alternative is when any site is a fuzzy circle and as a result the cells become fuzzy too.^{[10]}
Voronoi diagrams are also related to other geometric structures such as the medial axis (which has found applications in image segmentation, optical character recognition, and other computational applications), straight skeleton, and zone diagrams. Besides points, such diagrams use lines and polygons as seeds. By augmenting the diagram with line segments that connect to nearest points on the seeds, a planar subdivision of the environment is obtained.^{[11]} This structure can be used as a navigation mesh for path-finding through large spaces. The navigation mesh has been generalized to support 3D multi-layered environments, such as an airport or a multi-storey building.^{[12]}
Direct algorithms:
Starting with a Delaunay triangulation (obtain the dual):
Medicine, Statistics, Logic, Mathematics, Physics
Science, Computer science, Transhumanism, Engineering, Internet
Triangulation (geometry), Mathematics, Finite element method, Voronoi diagram, Computational geometry
Relational model, Acid, Database normalization, Sql, Parallel computing
Biology, Evolution, Earth science, Earth, Genetics
Computer science, Robotics, Randomized algorithm, Voronoi diagram, Space-filling tree
Computer graphics, Voronoi diagram, Polygon, Texture mapping, Texture filtering
University of Bath, Imperial College London, United Kingdom, The Guardian, Voronoi Diagram