## Duality between Voronoi and Delaunay DiagramsVoronoi 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 DiagramLet - 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 f_{1}and f_{2}be the faces incident to the two sides of the edge.- If f
_{1}and f_{2}are both bounded, then the edge c(f_{1})c(f_{2}) belongs to VD(S). - If f
_{1}is unbounded and f_{2}is bounded, then a ray with source c(f_{2}) and contained in the perpendicular bisector of s and t belongs to VD(S). It extends into the halfplane containing the unbounded face. - If f
_{1}and f_{2}are both unbounded and hence f_{1}=f_{2}, 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.
- If f
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:## Manual Entries |

Please send any suggestions, comments or questions to leda@algorithmic-solutions.com

© Copyright 2001-2003, Algorithmic Solutions Software GmbH