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 pi and S1 and is the locus of points closer to that point than to any other points [1].
Mathematically, let P = {p1, . . . , pn}, where
2
≤ n ≤ ∞
and xi
≠
xj for i ≠ j, i, j
In. The region given by
V(pi) = {x: || x - xi ||
≤
|| x - xj || for j ≠ i, i
In}
is called ordinary Voronoi polygon associated with pi or the Voronoi polygon of pi and the set given by
V = { V(pi), . . . , V(pn)}
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 = { pi, . . . , pn }
R2, where 2 ≤
n ≤ ∞
and xi
≠
xj
for i ≠
j, i, j
In. We call the region
the ordinary Voronoi polygon associated with pi and set V(P) = {V(p1), . . . , V(pn)} the planar ordinary Voronoi diagram generated by P.
Given a set S of
N points in the plane, for each
pi
S, what is the locus of points
(x, y) in the plane that are closer
to pi
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 θ(n2).
[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.
