Algorithmic Solutions > LEDA > LEDA Guide > Geometry Algorithms > Duality between Voronoi and Delaunay Diagrams

## 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.

Voronoi diagrams

Delaunay Diagrams

Geometry Algorithms

Geometry

### Manual Entries

Manual Page of Geometry Algorithms