 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
The Definition of Voronoi Diagrams
Voronoi Diagram: The Voronoi Diagram of a collection of geometric objects is a partition of space into cells, each of which consists of the points closer to one particular object than to any others.
| Voronoi diagram | Voronoi diagram |
|---|---|
 |
 |
| Points that make the Voronoi diagram | A Voronoi diagram constructed for those points |
Delaunay Triangulation: A Delaunay network in two dimensions consists of non-overlapping triangles where no points in the network are enclosed by the circumscribing circles of any triangle.
| Delaunay triangulation | Delaunay t. + Voronoi D. |
|---|---|
 |
 |
| Delaunay triangulation constructed for the same points | Delaunay T. and Voronoi D. constructed together on the same graphic |
History
The concept of Voronoi diagrams first appeared in works of
Descartes as early as 1644. Descartes used Voronoi-like diagrams to show the
disposition of matter in the solar system and its environs.
The first man who studied the Voronoi diagram as a concept was a German
mathematician G. L. Dirichlet. He studied the two- and three dimensional case
and that is why this concept is also known as Dirichlet tessellation. However it
is much better known as a Voronoi diagram because another German mathematician
M. G. Voronoi in 1908 studied the concept and defined it for a more general
n-dimensional case.
Very soon after it was defined by Voronoi it was developed independently in
other areas like meteorology and crystalography. Thiessen developed it in
meteorology in 1911 as an aid to computing more accurate estimates of regional
rainfall averages. In the field of crystalography German researchers dominated
and Niggli in 1927 introduced the term Wirkungsbereich (area of influence) as a
reference to a Voronoi diagram.
During the years this concept kept being rediscovered over and over again in
different fields of science and today it is extensively used in about 15
different fields of sciences. Some of them being mathematics, computer science,
biology, cartography, physiology and many others.
Source: Okabe, Boots, et. al., 1992 - For more
information look at the Reference page
If you want to check out all the fields and a short explanation of the uses
of Voronoi diagrams go to this page, it has the best list of Voronoi diagram
uses on the Net:
http://www.ics.uci.edu/~eppstein/gina/scot.drysdale.html
| Contact: Zdravko Jeremic [jeremicz@alum.beloit.edu] | posted: 07/25/97 | updated: 04/22/07 |