Pronunciation :American/English speakers pronounce “Voronoi” as "Vo - ro - noi" with a short "o" sound, like the "o" in "or", for the first two syllables. The third syllable is pronounced like the "noi" as in "noise". The stress is on the third syllable. On the other hand, Russian speakers pronounce the name with a short "o" in the first two syllables and it is such a short "o" that it almost sounds likes "uh" or even "ah".

Without loss of generality, suppose that a set of points is given in the Euclidean plane. The number of points is assumed to be two or more. Given this point set, the problem is to assign every location in the plane to the closest member in the point set. As a result, the set of locations assigned to each member in the point set forms its region. The set of locations assigned to two or more members in the point set forms the boundaries of the regions. Hence, adjacent regions are overlapped only on their boundaries. Thus, the set of the regions mutually exclusive except for boundaries. This collective regions (the set of regions) forms a tessellation. This tessellation is known as a planar ordinary Voronoi Diagram, and the regions constituting the Voronoi Diagram is called ordinary Voronoi Polygon.

Dirichlet or Thiessen tessellations are other names for Voronoi diagram. Dirichlet (1850) used a special form of the Voronoi tessellation in his study of positive quadratic forms. Voronoi later published a generalization of this concept that would apply to higher dimensions and so introduced the concept in its modern form. Individual investigators have used this powerful concept informally, at least as far back as Descartes in 1644.

A Voronoi Diagram for a set *S* of* *
* N* planar points is a partition of the plane
into *N* polygonal regions, each of which is associated with some point
*p _{i}* and

Mathematically, let *P* = {p_{1}, . . . , p* _{n}*}, where
2
≤

V(p* _{i}*) = {

is called ordinary Voronoi polygon associated with p_{i }or the
Voronoi polygon of p_{i } and the set given by

V = { V(p* _{i}*), . . . , V(p

is called the planar ordinary Voronoi diagram generated by
*P* or simply Voronoi diagram of
*P*.

We can also define a planar ordinary Voronoi diagram with half planes as
follows [2]: Let P = { p* _{i}*, . . . , p

the ordinary Voronoi polygon associated with p_{i }and set V(P) = {V(p_{1}), . . . , V(p_{n})} the planar ordinary Voronoi diagram generated by P.

Given a set *S* of
*N* points in the plane, for each
p_{i }
*S*, what is the locus of points
(*x*, *y*) in the plane that are closer
to p_{i
}than to any other point of S?

**Example 1
**Suppose we are given following points

A Voronoi diagram divides the drawing into a region around each point such that the borders of the regions are equidistance from the two nearest points.

**Example 2
**Suppose we have a few hundred environmental sampling
stations scattered throughout a region. Also, suppose that we have a eight data
collection centers (yellow points).

The problem is to assign each sampling station to the nearest collection center. The solution is to create a Voronoi Area around each data center (yellow points) as follows:

The incremental method is a powerful method for the construction of Voronoi
diagram. This method has been one of the most popular methods for studying the
concept of Voronoi diagram and for practical implementation. This method starts
with a simple Voronoi diagram for three sites and modifies the diagram by adding
a new point one at time. In the worst case, the addition of points is time
proportional to the number of points added so far. Consequently, the worst-case
time complexity is θ(n^{2}).

[1] F.P. Preparata and M.I. Shamos, "*Computational
Geometry*", Springer-Verlag, 1985.

[2] A. Okabe, B. Boots and k. Sugihara, "*Spatial Tessellations, Concepts and
Applications of Voronoi Diagrams*", John Wiley, 1995.

[3] P. J. Green and R. R. Sibson, "*Computing Dirichlet tessellations in the
plane*", Computer Journal vol. 21 n 2 (1978), p.168-173.

[4] T. Ohya, M. Iri and k. Murota, "*Improvements of the incremental method
for the Voronoi diagram with computational comparison of various algorithms*",
J. Operational Research Society, Japan 27 (4) (1984), p. 306-336.

[5] K. Sugihara and M. Iri, "*Construction of the Voronoi diagram for ‘one
million’ sites in single-precision arithmetic*", Proc. IEEE 80(9) (1992),
1471-1484.

[6] J. R. Sack and J. Urrutia, "*Handbook of Computational Geometry*",
Elsevier Science B. V. 2000.

[7]A. Okabe, B. Boots, and K. Sugihara, "*Spatial Tessellations Concepts and
Applications of Voronoi Diagrams*", John Wiley & Sons Ltd, 1992.