Voronoi diagrams

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. 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 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 to a large number of fields, mainly in science and technology but also including visual art.

Definition 4.3   The Voronoi digram $\mathcal{V}(S)$ of set $S$ of points, called $S = \{s_1, s_2, \dots, s_n\}$ in $\Re^k$ is a partition of $\Re^k$ into Voronoi cells $V(S_i)$, $i=1, 2, \dots, n$, such that each cell contains points that are closer to site $s_i$ than to any other site $s_j$, $j\neq i$, i.e.,

$$V(s_i) = \{x \in \Re^k \vert d(x, s_i) \leq d(x, s_j) \forall s_j \in \Re^k, j\neq i\}$$ (4.1)

Figure (a) shows the Vornoi diagram of 16 point sites in two dimensions. Figure (b) shows the straight line dual graph of the Voronoi diagram, which is also called Delaunary triangulation.

Figure: A Vornoi diagram of a set of 16 points in the plane.

In two dimensions, $\mathcal{V}(S)$ is a planar graph and is of size linear in $\vert S\vert$. In dimension $k \geq 2$, the total number of $d$-faces of dimensions $d= 0, 1, \dots, k-1$, in $\mathcal{V}(S)$ is $O(n^{d/2})$.

Construction of Voronoi diagram in two Dimensions. The Voronoi diagram possesses many properties that are proximity related. For instance, the closest pair problem for $S$ can be solved in linear time after the Voronoi diagram has been computed. Because this pair of points must be adjacent in the Denaunay triangulation, all one has to do is examine all adjacent pairs of points and report the pair with the smallest distance.

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 (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$ of a given shop $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:

	$$l_2$$	$$= d[(a_1, a_2), (b_1, b_2)]$$
		$$= \sqrt{(a_1 - b_1)^2+(a_2-b_2)^2}$$