A 2d **Delaunay triangulation** (DT) for a set P of points
in the plane is a triangulation such that no point in P is inside the
circumcircle of any triangle in the triangulation. It can be shown that for all
possible triangulations of P, a Delaunay triangulation maximizes the minimum
angle of all angles of the triangles in the triangulation.

Thus, a Delaunay triangulation tends to avoid “skinny” triangles. This property makes it the triangulation of choice for many purposes, including Digital Terrain Modelling (DTM).

Figure 31: A Delaunay triangulation with all circumcircles and their centres. Image available under GNU license at http://en.wikipedia.org/wiki/File:Delaunay_circumcircles_centers.png

A Delaunay triangulation is unique in a general case. It is not unique if four triangulation points lie on the same circle.

A 2d **conforming Delaunay triangulation** (CDT) is a
Delaunay triangulation that respects constraints (edges). This is done by
iteratively inserting additional points (called Steiner points) until no
triangle crosses a constraint.

Computational power

In general, triangulating pure point data is much faster than triangulation pure constraint data. This is because constraints are processed iteratively until no constraint crosses a triangle. Benchmarks for pure constraint data cannot be given because the number of iterations depends on the distribution of the constraints.

On an average 32bit machine, *ComputationalCAD* for
AutoCAD triangulates about 0.5M to 1M points in about one minute. This may
extend to several millions of points on a 64bit machine. The computational
complexity is , resulting in near-linear computation
time over the number of triangulation points. However, the maximum number of
triangulation points is limited by the available amount of memory.

Figure 32: Triangulation timings