Voronoi Diagrams & Delaunay Triangulation
Voronoi Diagrams / Dirichlet Tesselations
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.
so for a set S of n sites:
| Voronoi diagram VD(S): | the partition of the plane into blocks of points with the same nearest site or sites. |
|---|
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, hence the name Voronoi Diagrams. The Voronoi cells/polygons are sometimes also called Thiessen Polytopes or Dirichlet Regions.
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.
example of a Voronoi Diagram
Delaunay Triangulation
The Delaunay triangulation of a point set is a collection of edges satisfying an "empty circle" property: for each edge we can find a circle containing the edge's endpoints but not containing any other points.
The Delaunay triangulation is the dual structure of the Voronoi diagram
in R². By dual, we mean to draw a line
segment between two Voronoi vertices if their Voronoi polygons have a common
edge, or in more mathematical terminology: there is a natural bijection
between the two which reverses the face inclusions.
The circumcircle of a Delaunay triangle is called a Delaunay circle.
Delaunay triangulation, on top of the Voronoi diagram (in dotted lines)
References & More..
- Chapter 7 about Voronoi diagrams in "Computational Geometry: Algorithms and Applications, Second Edition" by Mark de Berg, Marc van Kreveld, Mark Overmars, Utrecht (the Netherlands) and Otfried Schwarzkopf, Hong Kong (China)
- Delaunay triangulation in two and three dimensions (Master thesis by Jörg Krämer, Dec.1995)
- The Voronoi website