Delaunay Triangulation

A triangulation of a point set in which no point lies inside the circumcircle of any triangle. It is the dual of the Voronoi diagram, and it is unique when no four points are concyclic.

Why it is the “right” triangulation

Among all triangulations of the same points, Delaunay:

• maximises the minimum angle (avoids skinny triangles) — and in fact maximises the whole sorted angle vector lexicographically;
• minimises the maximum circumcircle radius;
• contains the closest pair as an edge;
• contains the Euclidean minimum spanning tree as a subgraph;
• contains the nearest-neighbour graph as a subgraph.

The last two are the reasons it matters algorithmically.

Construction

Method	Time	Note
Flip algorithm	$O(n^2)$	start anywhere, flip illegal edges until none remain
Bowyer-Watson	$O(n\log n)$ expected	incremental; easiest to understand
Divide and conquer (Guibas-Stolfi)	$O(n\log n)$ worst case	quad-edge structure
Sweep line (Fortune)	$O(n\log n)$	build Voronoi and dualise
Lift to 3D + convex hull	$O(n\log n)$	the most elegant

The lifting map

Send $(x,y)\mapsto (x,y,x^2+y^2)$ onto the paraboloid. Then:

The lower convex hull of the lifted points, projected back to the plane, is the Delaunay triangulation.

A point is inside a circumcircle in 2D exactly when its lift is below the corresponding plane in 3D — so the in-circle predicate becomes an orientation test in 3D. If you have a 3D hull routine, you get Delaunay for free.

The in-circle predicate — the hard part

$\mathrm{inCircle}(a,b,c,d)=\mathrm{sign}\left|\begin{array}{ccc}{a}_x-d_x& a_y-d_y& |a-d{|}^2\\ b_x-d_x& b_y-d_y& |b-d{|}^2\\ c_x-d_x& c_y-d_y& |c-d{|}^2\end{array}\right|$

with $a,b,c$ counter-clockwise; positive means $d$ is strictly inside.

This determinant is degree 4

With coordinates up to $10^9$ it reaches $10^{45}$ — far beyond long long and beyond double’s 53-bit mantissa. Getting the sign wrong produces a non-triangulation, not a slightly wrong one.

Options: restrict coordinates to $\le 10^4$ and use __int128; use exact rational or big-integer arithmetic; or use adaptive-precision predicates (Shewchuk). This is the single biggest obstacle to implementing Delaunay correctly.

Uses

Problem	How
Euclidean MST	Delaunay has $O(n)$ edges and contains the EMST → Kruskal on those
Closest pair	the shortest Delaunay edge
Nearest neighbour graph	a subgraph
Largest empty circle	centred at a Voronoi vertex = a Delaunay circumcentre
Terrain / mesh generation	maximising the minimum angle avoids numerical trouble
Interpolation (natural neighbour)	uses the Voronoi structure
Point location	walk the triangulation

Euclidean MST, concretely

1. Build the Delaunay triangulation           O(n log n)
2. Take its O(n) edges with Euclidean weights
3. Run Kruskal                                 O(n log n)

Versus $O(n^2\log n)$ on the complete graph. For $n=10^5$ that is the difference between feasible and not.

Constrained Delaunay

Forces certain edges to appear (for meshing a polygon with fixed boundaries). The result is no longer strictly Delaunay — triangles may violate the empty-circle property, but only because of the forced edges.

3D and beyond

Delaunay tetrahedralisation exists in 3D but can have $\Theta (n^2)$ tetrahedra, and its construction is much harder. The lifting map still works (to 4D), and the in-sphere predicate has degree 5.

The contest reality

Full Delaunay implementations are long and precision-critical. Before writing one, check whether you actually need it:

• Euclidean MST with $n\le 5000$ → the complete graph is $1.2\cdot 10^7$ edges; just run Kruskal.
• Nearest neighbour queries → a KD-tree.
• Closest pair → the sweep.
• Largest empty circle → enumerate candidate centres.

Delaunay earns its place at $n\ge 10^5$ with a genuine Euclidean MST requirement.

See also: Voronoi Diagram · Bowyer-Watson · Convex Hull