Every other entry in this site's Geometry category starts from a shape that's already given —
segments, a polygon's own boundary — and answers a question about it. Polygon Triangulation comes closest to this page,
but it too starts from a fixed boundary and only decides how to cut its interior. Delaunay
Triangulation starts from nothing but a bare set of points and has to invent the connectivity itself:
given n points in the plane, connect them into a maximal set of non-crossing triangles
covering their convex hull. There are, in general, many ways to triangulate the same point set — but
exactly one of them (assuming no four points sit exactly on a common circle) satisfies the
Delaunay condition: for every triangle in the triangulation, no other point of the
set lies inside that triangle's circumcircle. This isn't an arbitrary tie-breaker. Among every valid
triangulation of a given point set, the Delaunay triangulation is the one that maximizes the smallest
angle appearing anywhere in it — it actively avoids the long, thin "sliver" triangles that make mesh
interpolation, terrain modeling, and nearest-neighbor queries behave badly.
The Bowyer-Watson algorithm builds it incrementally, one point at a time. Start
with any valid triangulation (even a trivial, wildly non-Delaunay one) and insert a new point p
into it: find every triangle whose circumcircle contains p — call these triangles
bad — remove them all, which opens up a single polygonal hole in the mesh, then
retriangulate that hole by connecting p to every edge on the hole's boundary. Every
triangle in the result either survived untouched or has p as one of its own vertices, so
none of them can have p inside their circumcircle anymore, and it can be shown that no
previously-satisfied triangle stops satisfying the condition either. Repeat for every point and the
final mesh is Delaunay.
Eight points, inserted in the fixed order shown by their numeric labels. Step through and watch two things: how many bad triangles get removed and how many new ones fan out from each freshly inserted point, and how long it takes before any real triangle becomes visible at all. The algorithm has to start from a valid triangulation before it has any real points to work with, so it bootstraps with one giant triangle far outside this canvas, invisible by construction — every triangle still touching one of that triangle's three corners is scaffolding, not part of the answer, and gets discarded only once the real points have grown enough structure to replace it completely.
The correctness argument rests on one geometric fact: when a new point p lands inside
the current triangulation, the set of bad triangles (the ones whose circumcircle contains p)
is always edge-connected and star-shaped from p's own
position — no matter how scattered the triangulation looks, the bad region is always a single
simply-connected blob, never several separate islands, and every point on its boundary is directly
visible from p with no other bad triangle in the way. That's what makes "collect every
edge that belongs to exactly one bad triangle, then connect each of those boundary edges straight to
p" a valid way to retriangulate the hole: a star-shaped polygon can always be fanned from
any point that sees its whole boundary, and p is guaranteed to be exactly such a point for
this specific hole. The edges shared between two bad triangles are interior to the hole and simply
vanish; only the boundary survives, and it survives as new triangles instead of an old one.
This is the same underlying test as the more mechanical edge-flip view of Delaunay
triangulation: an edge shared by two triangles is "locally Delaunay" if flipping it — replacing it with
the other diagonal of the quadrilateral the two triangles form — would not improve either
triangle's circumcircle test. Bowyer-Watson never explicitly flips anything, but removing a bad
triangle and refilling its space from p has exactly the same effect: every edge that
survives into the new mesh is one no single flip could improve, for the same reason every one of the
newly-formed triangles has an empty circumcircle by construction.
function inCircumcircle(a, b, c, p) {
// requires a, b, c listed counterclockwise
if (cross(a, b, c) < 0) { const t = b; b = c; c = t; }
const ax = a.x - p.x, ay = a.y - p.y;
const bx = b.x - p.x, by = b.y - p.y;
const cx = c.x - p.x, cy = c.y - p.y;
const det = (ax * ax + ay * ay) * (bx * cy - cx * by)
- (bx * bx + by * by) * (ax * cy - cx * ay)
+ (cx * cx + cy * cy) * (ax * by - bx * ay);
return det > 0;
}
function superTriangle(points) {
let minX = Infinity, minY = Infinity, maxX = -Infinity, maxY = -Infinity;
for (const p of points) {
minX = Math.min(minX, p.x); minY = Math.min(minY, p.y);
maxX = Math.max(maxX, p.x); maxY = Math.max(maxY, p.y);
}
// The margin below isn't cosmetic — see Pitfalls. Too small and real area silently vanishes.
const span = Math.max(maxX - minX, maxY - minY, 1) * 1e6;
const midX = (minX + maxX) / 2, midY = (minY + maxY) / 2;
return [
{ x: midX - span, y: midY - span, super: true },
{ x: midX + span, y: midY - span, super: true },
{ x: midX, y: midY + span, super: true },
];
}
function delaunay(points) {
let triangles = [superTriangle(points)];
for (const p of points) {
const bad = triangles.filter(t => inCircumcircle(t[0], t[1], t[2], p));
const edgeCount = new Map();
for (const t of bad) {
for (const [u, v] of [[t[0], t[1]], [t[1], t[2]], [t[2], t[0]]]) {
const key = edgeKey(u, v);
if (!edgeCount.has(key)) edgeCount.set(key, { count: 0, edge: [u, v] });
edgeCount.get(key).count++;
}
}
const boundary = [...edgeCount.values()].filter(e => e.count === 1).map(e => e.edge);
triangles = triangles.filter(t => !bad.includes(t));
for (const [u, v] of boundary) triangles.push([u, v, p]);
}
return triangles.filter(t => !t.some(v => v.super));
}An ordinary-looking, plenty-large bounding triangle can still silently drop real area from
the result — and no per-triangle check catches it, because every triangle that ships is individually
still Delaunay-valid. An early version of superTriangle above sized its margin
at 20× the point set's own bounding-box span — visually enormous, and correct on every point set
tried by hand. Verifying it the same way Polygon
Triangulation verifies its own tiling, by summing every output triangle's area with the shoelace
formula and comparing against the point set's convex hull area, turned up a concrete 9-point
configuration where the two numbers disagree by exactly 205 square units — a real, triangle-shaped hole,
not rounding noise. The missing triangle, (438, 62)–(485, 437)–(472, 342), never got built: a leftover
triangle still touching the invisible super-triangle survived untouched to the very end, because
neither of the point set's own last two points happened to land inside its circumcircle (confirmed
with exact integer arithmetic, not floating-point, to rule out precision as the cause) — and the final
cleanup step that strips every triangle touching the scaffold threw away its real area along with it.
Reran the same 9 points through 1,000 random shuffles of insertion order: every single one reproduced
the identical hole, ruling out an unlucky insertion order as the cause. Cross-checked against a
completely different Delaunay construction — fan-triangulate the convex hull, insert each interior
point by splitting whichever triangle contains it, then repeatedly flip any locally-non-Delaunay edge
until none remain — and that independent method does produce the missing triangle, confirming
the bug was in the undersized margin, not the verification method. Scaling the margin up to
1,000,000× the bounding-box span, as shown above, fixed this exact configuration and came back
clean across 10,000 further random point sets (372,307 triangles checked in total): zero area-coverage
gaps, zero circumcircle violations. "Large enough to contain every point" and "large enough for the
algorithm to actually converge to the right answer" are different requirements, and the gap between
them isn't obvious from staring at any one point set that happens to work.
Time: O(n²) as shown above. Each of the n insertions
scans every triangle currently in the mesh to test its circumcircle, and the mesh has O(n)
triangles at any point, so each insertion costs O(n) with no shortcuts. Randomizing the
insertion order and adding a point-location structure that lets each new point's search resume from
roughly where the last one landed — the same randomized-incremental idea behind the still-unbuilt
trapezoidal map named on Slab Decomposition and Point in Polygon's own Complexity sections — brings the
expected cost down to O(n log n), the standard real-world bound for Delaunay
triangulation; this page's reference implementation trades that speed for the simplicity of a single
brute-force scan. Space: O(n) for the mesh itself.
A Delaunay triangulation's dual graph — connect the circumcenters of every pair of triangles that share an edge — is the Voronoi diagram of the same point set: the partition of the plane into regions of "closest to this point." Built as its own entry, which confirms the duality directly against this page's own triangulation of the same 8 points.
This triangulation also has a direct use outside computational geometry: for points in the plane,
it's guaranteed to contain the Euclidean minimum spanning tree as a subgraph, so
restricting Kruskal's algorithm to just its O(n)
edges instead of every one of the O(n²) possible pairs still finds the exact same tree.
Built as its own entry.
This site's guide, Choosing a Geometry Algorithm, places this entry as the route to take when the input is only a bare point set with no boundary and triangles themselves are the goal — it also carries a second structure for free, the dual Voronoi Diagram.