Voronoi diagrams were first discussed by Peter Lejeune-Dirichlet in 1850. But it was more than a half of a century later in 1908 that these diagrams were written about in a paper by Voronoi and hence the name Voronoi diagrams.
A Voronoi diagram is a geometric structure that represents proximity information about a set of points or objects. Given a set of sites or objects, the plane is partitioned by assigning to each point its nearest site. The points whose nearest site are not unique form the Voronoi diagram. That is, the points on the Voronoi diagram are equidistant to two or more sites.
Voronoi diagrams have numerous applications in areas ranging from archaeology to zoology. For instance, Voronoi diagrams are essential in the solution to a wireless communication problem. Given a set of n micro-cell substations, how can they be pre-processed so that for any arbitrary cellular call the closest substation will carry the call?
There are a variety of algorithms available to construct Voronoi diagrams. One popular method is the incremental algorithm that adds a new site to an already existing diagram. In 1985, Steve Fortune developed a plane-sweep algorithm which is more efficient in time than any incremental algorithm.
Voronoi diagrams may be generalized in several different ways each with considerable practical applications. Voronoi diagrams in three dimensions are used in crystallography studies to simulate growth rates. Voronoi diagrams can be constructed not only for sites that are points but also polygons. These polygon Voronoi diagrams are analyzed in motion planning.
GLOSSARY TERMS
site - one of the points in the set for which a Voronoi diagram is to be computed
Voronoi region of site S - a set of points closer to a site S than any other site
Voronoi edge - the boundary between two Voronoi regions
Voronoi vertex - a point at which three or more Voronoi edges meet
relevant pairs of sites - pairs of sites that are near enough to each other to share a Voronoi edge. There exists a circle that passes through both sites and has no other site in its interior.