Voronoi diagram

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. 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. It is named after Georgy Voronoi, and is also called a Voronoi tessellation, a Voronoi decomposition, a Voronoi partition, or a Dirichlet tessellation (after Peter Gustav Lejeune Dirichlet). Voronoi diagrams have practical and theoretical applications in a large number of fields, mainly in science and technology, but also in visual art.They are also known as Thiessen polygons. In the simplest case, shown in the first picture, we are given a finite set of points {p1, ..., pn} in the Euclidean plane. In this case each site pk is simply a point, and its corresponding Voronoi cell Rk consists of every point in the Euclidean plane whose distance to pk is less than or equal to its distance to any other pk. Each such cell is obtained from the intersection of half-spaces, and hence it is a convex polygon. The line 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 X { extstyle X} be a metric space with distance function d { extstyle d} . Let K { extstyle K} be a set of indices and let ( P k ) k ∈ K { extstyle (P_{k})_{kin K}} be a tuple (ordered collection) of nonempty subsets (the sites) in the space X { extstyle X} . The Voronoi cell, or Voronoi region, R k { extstyle R_{k}} , associated with the site P k { extstyle P_{k}} is the set of all points in X { extstyle X} whose distance to P k { extstyle P_{k}} is not greater than their distance to the other sites P j { extstyle P_{j}} , where j { extstyle j} is any index different from k { extstyle k} . In other words, if d ( x , A ) = inf { d ( x , a ) ∣ a ∈ A } { extstyle d(x,,A)=inf{d(x,,a)mid ain A}} denotes the distance between the point x { extstyle x} and the subset A { extstyle A} , then The Voronoi diagram is simply the tuple of cells ( R k ) k ∈ K { extstyle (R_{k})_{kin 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 R k { extstyle R_{k}} is associated with a generator point P k { extstyle P_{k}} .Let X { extstyle X} be the set of all points in the Euclidean space. Let P 1 { extstyle P_{1}} be a point that generates its Voronoi region R 1 { extstyle R_{1}} , P 2 { extstyle P_{2}} that generates R 2 { extstyle R_{2}} , and P 3 { extstyle P_{3}} that generates R 3 { extstyle R_{3}} , 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'. 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 R k {displaystyle scriptstyle R_{k}} of a given shop P k {displaystyle 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 familiarEuclidean distance: ℓ 2 = d [ ( a 1 , a 2 ) , ( b 1 , b 2 ) ] = ( a 1 − b 1 ) 2 + ( a 2 − b 2 ) 2 {displaystyle ell _{2}=dleft={sqrt {left(a_{1}-b_{1} ight)^{2}+left(a_{2}-b_{2} ight)^{2}}}} or the Manhattan distance: d [ ( a 1 , a 2 ) , ( b 1 , b 2 ) ] = | a 1 − b 1 | + | a 2 − b 2 | {displaystyle dleft=left|a_{1}-b_{1} ight|+left|a_{2}-b_{2} ight|} . The corresponding Voronoi diagrams look different for different distance metrics.