17.14 Delaunay Triangulation Overview

Given a set of points in the plane, construct a triangulation that avoids thin, poorly shaped triangles as much as possible.

algorithmsgeometry

17.14 Delaunay Triangulation Overview

Problem

Given a set of points in the plane, construct a triangulation that avoids thin, poorly shaped triangles as much as possible.

A triangulation connects points with noncrossing edges so that the convex hull is divided into triangles.

Many triangulations are possible for the same point set. Some produce skinny triangles, which are undesirable in interpolation, finite element methods, rendering, terrain modeling, and mesh generation.

The Delaunay triangulation is the standard answer for many practical applications because it tends to maximize the minimum angle of the triangles.

Solution

Build a triangulation in which no point lies strictly inside the circumcircle of any triangle.

This condition is called the empty circumcircle property.

For every triangle:

A, B, C

draw the unique circle passing through those three vertices.

The triangulation is Delaunay if no other input point lies inside that circle.

       B
     /   \\n    /     \\n   A-------C

circle through A, B, C contains no other site

This local geometric condition produces a globally useful triangulation.

Why Delaunay Triangulations Matter

Delaunay triangulations are useful because they avoid unnecessarily narrow triangles.

They are not perfect: some input point sets force skinny triangles. But among all triangulations of the same point set, Delaunay triangulations have strong angle-quality properties.

They are used in:

mesh generation
terrain modeling
surface reconstruction
nearest-neighbor graphs
finite element preprocessing
geographic analysis
computer graphics
robotics

The triangulation is also the dual of the Voronoi diagram.

Two points are connected by a Delaunay edge exactly when their Voronoi cells share an edge.

Delaunay and Voronoi Duality

The relationship is structural:

Voronoi diagram:
    partitions space into nearest-site cells

Delaunay triangulation:
    connects sites whose cells touch

If two Voronoi cells share an edge, their generating sites are neighbors.

Draw an edge between those sites.

Doing this for all adjacent Voronoi cells produces the Delaunay triangulation.

This duality gives a conceptual construction:

build Voronoi diagram
connect neighboring sites

In practice, many algorithms construct Delaunay triangulations directly.

The Empty Circumcircle Test

Given triangle:

A, B, C

and point:

P

the key predicate is:

is P inside the circumcircle of A, B, C?

This is called the in-circle test.

The result determines whether a triangulation edge is locally legal.

If point P lies inside the circumcircle of triangle ABC, then the current triangulation violates the Delaunay condition.

This violation can often be fixed by flipping an edge.

Edge Flipping

Consider a convex quadrilateral with diagonal:

A-----B
 \   /
  \ /
  / \\n /   \\nD-----C

There are two possible diagonals:

AC

and:

BD

If the current diagonal creates triangles that violate the Delaunay condition, flip it.

Before:

triangles ABC and ACD

After:

triangles ABD and BCD

Edge flipping is the basis of several Delaunay algorithms.

Local Delaunay Condition

An interior edge is locally Delaunay if the opposite vertex of either adjacent triangle does not lie inside the circumcircle of the other triangle.

For edge:

AC

with adjacent triangles:

ABC
ACD

check whether:

D is inside circumcircle(A,B,C)

or equivalently whether:

B is inside circumcircle(A,C,D)

If the test fails, flip the edge.

Repeatedly flipping illegal edges eventually reaches a Delaunay triangulation under standard assumptions.

Incremental Construction

A common construction method is randomized incremental insertion.

The outline:

start with a large enclosing super-triangle
insert points one at a time
find the triangle containing the new point
split that triangle
repair illegal edges by flips
remove triangles touching the super-triangle

This algorithm is conceptually approachable and works well with suitable point-location support.

Basic sketch:

def delaunay(points):
    triangulation = make_super_triangle(points)

    for point in points:
        triangle = find_containing_triangle(triangulation, point)
        split_triangle(triangulation, triangle, point)
        legalize_edges(triangulation, point)

    remove_super_triangle_faces(triangulation)

    return triangulation

The omitted routines are substantial. Delaunay triangulation is less about a short implementation and more about getting predicates, topology, and degeneracies right.

Bowyer-Watson Algorithm

Another popular incremental method is the Bowyer-Watson algorithm.

For each inserted point:

  1. Find all triangles whose circumcircles contain the point.
  2. Remove those triangles.
  3. The removed triangles form a polygonal cavity.
  4. Retriangulate the cavity by connecting the new point to each boundary edge.

Sketch:

def insert_point(triangulation, point):
    bad = [
        triangle
        for triangle in triangulation.triangles
        if in_circumcircle(triangle, point)
    ]

    boundary = cavity_boundary(bad)

    for triangle in bad:
        triangulation.remove(triangle)

    for edge in boundary:
        triangulation.add_triangle(edge.a, edge.b, point)

This is often easier to explain than edge-flip incremental construction, but it still requires robust handling of topology and numerical predicates.

Super-Triangle

Incremental algorithms often begin with a triangle large enough to contain every input point.

        S1
       /  \\n      /    \\n     /      \\n    / points \\n   S2--------S3

After all points are inserted, any triangle using one of the super-triangle vertices is discarded.

This avoids boundary special cases during insertion.

The super-triangle must be large enough that all real points lie strictly inside it.

Degenerate Cases

Delaunay triangulation has important degeneracies.

Duplicate points should be removed before construction.

Collinear point sets do not produce a proper triangulation.

Four or more cocircular points create non-unique Delaunay triangulations.

Near-cocircular points are numerically unstable when using floating-point predicates.

Production-quality implementations usually use exact or adaptive predicates for orientation and in-circle tests.

Complexity Analysis

With efficient point location, randomized incremental Delaunay triangulation runs in expected:

O(n log n)

time.

Without efficient point location, repeatedly searching for the containing triangle can degrade to:

O(n²)

The triangulation itself has linear size:

O(n)

for planar point sets under standard assumptions.

Memory usage is therefore:

O(n)

plus auxiliary structures for point location and topology.

Correctness Argument

The Delaunay condition is defined by the empty circumcircle property.

Incremental algorithms maintain this property after each insertion.

When a point is inserted, only triangles whose circumcircles contain the new point can become invalid. Removing or flipping the affected local region restores the empty circumcircle condition.

Because unaffected triangles remain legal, and the local repair eliminates all new violations, the final triangulation satisfies the Delaunay condition.

Applications

Mesh Generation

Delaunay triangulations avoid many thin triangles and are a standard foundation for triangular meshes.

Terrain Modeling

Irregular terrain samples can be connected into a triangulated irregular network.

Interpolation

Delaunay neighbors provide natural local neighborhoods for interpolation.

Voronoi Construction

The Voronoi diagram can be recovered as the geometric dual of the Delaunay triangulation.

Nearest-Neighbor Graphs

Delaunay edges connect spatially meaningful neighbors and contain useful proximity information.

Common Pitfalls

Using Floating-Point In-Circle Tests Naively

The in-circle predicate is sensitive near degeneracy. Small numerical errors can produce invalid topology.

Forgetting to Remove Super-Triangle Faces

The final triangulation must not contain artificial vertices.

Mishandling Duplicate Points

Duplicates create zero-area triangles and undefined circumcircles.

Assuming Uniqueness

If four or more points are cocircular, multiple valid Delaunay triangulations may exist.

Ignoring Topological Consistency

A Delaunay implementation must update triangle adjacency, edge ownership, and cavity boundaries carefully.

Discussion

Delaunay triangulation is one of the central structures in computational geometry. It pairs naturally with Voronoi diagrams, provides high-quality triangulations for many point sets, and supports a wide range of spatial algorithms.

For a cookbook implementation, the important lesson is the role of predicates. Orientation tests keep triangle orientation consistent. In-circle tests detect illegal triangles. Edge flips or cavity retriangulation repair local violations. The algorithmic idea is compact, but robust implementation requires disciplined handling of degeneracy and topology.