SpecializedSource checked

Bowyer-Watson Algorithm

Builds a Delaunay triangulation by inserting points and retriangulating invalid cavities.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Geometry
Difficulty: Advanced
Family: Delaunay Triangulation
Tier: Specialized
Status: Verified
Review: Source Checked
Sources: 4
Formulas: 1
Relationships: 3
Code example: Ready
Visualization: Ready

Overview

Bowyer-Watson starts from a large containing triangle, inserts points one at a time, removes triangles whose circumcircles contain the new point, and fills the cavity.

Core Concepts

incremental insertioncircumcircle testcavity boundarytriangle mesh

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n log n)

Average

O(n log n) with spatial search

Worst

O(n^2)

Space

O(n)

When to Use

Use when points arrive incrementally or a straightforward Delaunay implementation is desired.
Use when mesh generation is a central requirement.

When Not to Use

Avoid when exact robustness is required but robust predicates are unavailable.
Avoid when floating-point precision or degenerate geometry cannot be handled robustly.

What It Does

Inserts points incrementally
Finds triangles with invalid circumcircles
Retriangulates the cavity boundary

Use Cases

Mesh generation
Terrain triangulation
Voronoi dual construction

Inputs

2D point set

Outputs

Delaunay triangle mesh

Key Formulas (1)

Delaunay condition

point is invalidating if point lies inside circumcircle(triangle)

point is invalidating if point lies inside circumcircle(triangle)

Identifies triangles that must be removed when inserting a point.

Pseudocode

1.Create a super-triangle containing all points
2.Insert each point
3.Find triangles whose circumcircles contain the point
4.Remove those triangles to form a cavity
5.Connect the new point to cavity boundary edges

Canonical Example

Input: points = triangle plus center point
Output: triangles = three triangles around center
Explanation: The inserted center point retriangulates the containing triangle.

Implementation Notes

Use a spatial index to find affected triangles faster than scanning all triangles.
Use robust predicates or tolerances when near-degenerate inputs are expected.
Keep a tiny example with expected output beside the implementation.

Common Pitfalls

Forgetting to remove super-triangle-connected faces leaves artificial triangles in the output.
Collinear, overlapping, and duplicate points need explicit tie-breaking rules.
Not defining boundary, empty, or degenerate inputs before implementation.