Algorithmic Solutions > LEDA > LEDA Guide > Geometry Algorithms > Delaunay Diagrams

## Delaunay Diagrams

A Delaunay diagram of a set `S` of points consists of the segments that belong to all (furthest site) Delaunay triangulations of `S`.

 On the right you see a Delaunay diagram of a set of four points placed at the corners of a square. The two possible Delaunay triangulations for the points can be build from the diagram by adding one of the two diagonals of the square. The picture is a screenshot from the example of computing and verifying a Delaunay diagram. ### Properties of Delaunay Diagrams

• A Delaunay diagram is a subgraph of every Delaunay triangulation.
• The Delaunay diagram is a planar graph whose bounded faces are convex polygons all of whose vertices are co-circular.
• If no four points of S are co-circular then all bounded faces are triangles and the Delaunay diagram is a triangulation.

### Running Time

The running time of the algorithms is O(n2).

### Verifying Delaunay Diagrams

The function
```	bool Is_Delaunay_Diagram(const GRAPH<POINT,int>& G,
delaunay_voronoi_kind kind)```

checks whether `G` is a Delaunay diagram of the points associated with its nodes. The flag `kind` allows to choose between the nearest (`kind=NEAREST`) and furthest (`kind=FURTHEST`) site version. See also Verification of Geometric Structures.

We use the notation `POINT` to indicate that the algorithm works both for `points` and `rat_points`. See also Writing Kernel Independent Code.

Data Types for 2-D Geometry

Delaunay Triangulations

Voronoi Diagrams

Euclidean Minimum Spanning Trees

Convex Hulls

Triangulations

Verification of Geometric Structures

Geometry Algorithms

Geometry

GeoWin

### Manual Entries

Manual Page of Geometry Algorithms