A triangulation of a set
S of points is a partition
of the convex hull of
triangles. This assumes that not all points of
S are collinear.
A triangulation is called Delaunay if the interior of the circumcircle
of any triangle in the triangulation contains no points of
If all points of
S are on the convex hull there is also
a so-called furthest site Delaunay triangulation. In a furthest
site Delaunay triangulation the circumcircle of any triangle has no points
of S in its exterior.
Properties of Delaunay Triangulations
- A Delaunay triangulation maximizes the smallest interior angle of
- Delaunay triangulations tend to "rounder" triangles than other triangulations.
This property is desirable for numerical applications.
- Delaunay triangulations are useful in many contexts.
- The Delaunay triangulation of a set of points is in general not unique.
The triangulation is represented by the parameterized
G is a straight
line embedded plane map. It corresponds to the triangulation
of the set of points
L as follows:
- Nodes are in one-to-one correspondence with the points in
G is bidirected
- For each node
G the list
of edges out of
v is ordered cyclically. This cyclic ordering
agrees with the counter-clockwise ordering of the edges incident to
the point in
T corresponding to
- Each edge
G has an integer label that
gives information about the edge.
The running time of the algorithms is O(n2).
Verifying Delaunay Triangulations
bool Is_Delaunay_Triangulation(const GRAPH<POINT,int>& G,
G is a Delaunay triangulation of the points
associated with its nodes. The flag
kind allows to choose
between the nearest (
kind==NEAREST) and furthest (
site version. See also Verification of Geometric
We use the notation
POINT to indicate that the algorithm works both
rat_points. See also Writing
Kernel Independent Code.
Algorithms for Constrained Delaunay Triangulations
LEDA provides additional algorithms for computing Delaunay triangulations
of segments, plane maps. Details can be found on the Manual
Page of Geometry Algorithms.
Types for 2-D Geometry
Verification of Geometric Structures
Writing Kernel Independent Code
Page of Geometry Algorithms