In mathematics, a **Voronoi diagram** is a special kind of decomposition of a given space, e.g., ametric space, determined by distances to a specified family of objects (subsets) in the space. These objects are usually called the sites or the generators (but other names such as “seeds” are in use) and to each such an object one associates a corresponding Voronoi cell, namely the set of all points in the given space whose distance to the given object is not greater than their distance to the other objects. It is named after **Georgy Voronoi**, and is also called a **Voronoi tessellation**, a **Voronoi decomposition**, or a **Dirichlet tessellation** (after Lejeune DirichletVoronoi diagrams can be found in a large number of fields in science and technology even in art and they have found numerous practical and theoretical applications.

**The simplest case**

In the simplest case (shown in the first picture), we are given a finite set of points *S={p _{1},…,p_{n}}* in the Eucledean planeIn this case each site

*p*is simply a point, and its corresponding Voronoi cell (also called Dirichlet cell)

_{k}*V*consisting of all points whose distance to

_{k}*p*is not greater than their distance to any other site. Each such a cell is obtained from the intersection of half-spaces, and hence it is a convexpolygon. 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.

_{k}**General definition**

Let *X* be a space (a nonempty set endowed with a distance function *d*. Let *(P _{k})_{k }*

_{∈}*be a family of nonempty subsets (the sites) in the space*

_{ K}*X*. The Voronoi cell

*V*associated with the site

_{k}*P*is the set of all points in

_{k}*X*whose distance to

*P*is not greater than their distance to the other sites

_{k}*P*, where j is any index different from k. In other words, if

_{j}*d(x,A)=inf{d(x,a): a in A}*denotes the distance between the point x and the subset A, then

*V _{k}={x in X: d(x,P_{k}) ≤ d(x,P_{j}) for all j≠k}*.

The Voronoi diagram is the family of cells *(V _{k})_{k }_{∈ K}* . In the particular case where the space is a Euclidean spaceand each site is a point, then the Voronoi cells are convex polygons 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.

**Illustration**

As a simple illustration, consider a family of shops, or other facilities such as post offices of supermarkets, in some flat city. Suppose we want to estimate the number of costumers of a given shop. Suppose further that the shops offer roughly the same products with roughly the same quality of service and price. Then it is reasonable to assume that costumers choose their preferred shop simply by distance considerations: they will go to the shop located nearest to them. In this case the Voronoi cell *V _{k}* of a given shop

*P*can be used for giving a rough estimate on the number of potential costumers going to this shop. Ideally, and in the simplest case, each such a shop is represented by a point. However, in reality a shop has a shape which is more complicated than just a mathematical point. In addition, we may want to consider a firm of shops, and in this latter case each site will represent the shops of a given firm, and in particular it may not be a connected set.

_{k}So far it was assumed that the distance between points in the city are measured using the standard distance, namely the Euclidean distance: *d((a _{1},a_{2}),(b_{1},b_{2}))=((a_{1}-b_{1})^{2}+(a_{2}-b_{2})^{2})^{0.5}*. However, if we consider the case where costumers only go to the shops by a vehicle and the traffic paths are parallel to the x and y axes, like in Mahattan, then a more realistic distance function will be the

*l*distance, namely

_{1}*d((a*.

_{1},a_{2}),(b_{1},b_{2}))=|a_{1}-b_{1}|+|a_{2}-b_{2}|**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.
- If the space is a normed space and the distance to each site is attained (e.g., when a site is a compact set or a closed ball), then each Voronoi cell can be represented as the union of line segments emanating from the sites.
- Under relatively general conditions (the space is a possibly infinite dimensional uniformly convex space, there can be infinitely many sites of a general form, etc.) Voronoi cells enjoy a certain stability property: a small change in the sites, e.g., by a translation or distortion, yields a small change in the shape of the Voronoi cells. This is the geometric stability of Voronoi diagrams.

**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. Thissen. In condensed matter physics, such tessellations are also known as Wigner-Seitz unit cells. Voronoi tessellations of the reciprocal lattice of momentra 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; note that the rectangles and the squares can also be generated by other lattices (for example the lattice defined by the vectors (1,0) and (1/2,1/2) gives squares). See here for a dynamic visual example.
- A 3D cubic lattice gives the cubic honeycomb
- Parallel planes with regular triangular lattices aligned with each others’ centers give the hexagonal prismatic honeycomb
- Certain body centered tetragonal lattices give a tessellation of space with rhombo-hexagonal dodecahedra
- 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 *n*th-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*.

**Farthest-Point Voronoi Diagram**

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 *P* = {*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*} be the convex hull of

_{k}*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*if and only if

_{i}*dist(q,*h

_{i}

*) > dist(q,*p

_{j}

*)*for each

*p*∈

_{j}*P*with

*h*≠

_{i}*p*. Where

_{j}*dist(p, q)*is the Euclidean distance between two points

*p*and

*q*.

**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 thestraight 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 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**

- One of the early applications of Voronoi diagrams was by John Snow to study the epidemology of the 1854 Broad Street cholera outbreak in Soho, England. He showed the correlation between areas on the map of London using a particular water pump, and the areas with most deaths due to the outbreak.
- 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, one might want 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.
- Voronoi diagrams together with Farthest-Point Voronoi diagrams are used for efficient algorithms to compute the roundness of a set of points.
- 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.
- Voronoi Polygons have been used in miningto estimate the reserves of valuable materials, minerals or other resources. Exploratory drillholes are used as the set of points in the Voronoi polygons.

***RME class**

http://en.wikipedia.org/wiki/Voronoi_diagram#The_simplest_case

Nice article. Its realy good. More information help me.

Thanks..

I hope this site can help everybody in the world, especially for children and teachers..