Delaunay triangulation

Special cases where this relationship does not hold, or is ambiguous, include cases like: For a set P of points in the (d-dimensional) Euclidean space, a Delaunay triangulation is a triangulation DT(P) such that no point in P is inside the circum-hypersphere of any d-simplex in DT(P).

This may be done by giving each point p an extra coordinate equal to |p|2, thus turning it into a hyper-paraboloid (this is termed "lifting"); taking the bottom side of the convex hull (as the top end-cap faces upwards away from the origin, and must be discarded); and mapping back to d-dimensional space by deleting the last coordinate.

If two triangles do not meet the Delaunay condition, switching the common edge BD for the common edge AC produces two triangles that do meet the Delaunay condition: This operation is called a flip, and can be generalised to three and higher dimensions.

This leads to a straightforward algorithm: construct any triangulation of the points, and then flip edges until no triangle is non-Delaunay.

[8] The most straightforward way of efficiently computing the Delaunay triangulation is to repeatedly add one vertex at a time, retriangulating the affected parts of the graph.

It gives an alternative to edge flipping for computing the Delaunay triangles containing a newly inserted vertex.

Blelloch et al.[14] proposed another version of incremental algorithm based on rip-and-tent, which is practical and highly parallelized with polylogarithmic span.

A divide and conquer algorithm for triangulations in two dimensions was developed by Lee and Schachter and improved by Guibas and Stolfi[9][15] and later by Dwyer.

[19][20] Sweephull[21] is a hybrid technique for 2D Delaunay triangulation that uses a radially propagating sweep-hull, and a flipping algorithm.

The sweep-hull is created sequentially by iterating a radially-sorted set of 2D points, and connecting triangles to the visible part of the convex hull, which gives a non-overlapping triangulation.

For example, smoothing (also referred to as mesh refinement) is one such method, which repositions nodes to minimize element distortion.

The stretched grid method allows the generation of pseudo-regular meshes that meet the Delaunay criteria easily and quickly in a one-step solution.

Constrained Delaunay triangulation has found applications in path planning in automated driving and topographic surveying.

A Delaunay triangulation in the plane with circumcircles shown
Example steps
Each frame of the animation shows a Delaunay triangulation of the four points. Halfway through, the triangulating edge flips showing that the Delaunay triangulation maximizes the minimum angle, not the edge-length of the triangles.
We need a robust and fast way to detect if point D lies in the circumcircle of A, B, C
A Delaunay triangulation of a random set of 100 points in a plane.