Duality between Voronoi and Delaunay Diagrams
Voronoi diagrams and Delaunay
diagrams are closely related structures. Each one is easily obtained
from the other.
How to Compute the Voronoi Diagram from the Delaunay Diagram
Let S be a set of sites. Let VD(S) the Voronoi
diagram of S and DD(S) the Delaunay diagram
of S.
- For every bounded face of
DD(S) there is a vertex c(f)
of VD(S) located at the center of the circumcircle of f.
- Consider an edge st of
DD(S) and let f1
and f2 be the faces incident to the two sides
of the edge.
- If f1 and f2
are both bounded, then the edge c(f1)c(f2)
belongs to VD(S).
- If f1 is unbounded and f2
is bounded, then a ray with source c(f2)
and contained in the perpendicular bisector of s and t belongs to
VD(S). It extends into the halfplane containing the unbounded face.
- If f1 and f2
are both unbounded and hence f1=f2,
then the entire perpendicular bisector of s and t belongs to VD(S).
(This case only arises if all sites are collinear.) Obtaining the
Delaunay diagram DD(S) of a point set S for the corresponding Voronoi
diagram can be done by a similar procedure.
Obtaining the Delaunay diagram DD(S) of a point set S for the corresponding
Voronoi diagram can be done by a similar procedure.
|
See also:
Voronoi diagrams
Delaunay Diagrams
Data Types for 2-D Geometry
Geometry Algorithms
Geometry
Manual Entries
Manual
Page of Geometry Algorithms
|