Delaunay Triangulation

Scatter a handful of points on a page and connect them into triangles so that the triangles tile the whole convex region without overlapping. There are usually many ways to do this — and most of them are ugly. You get long, needle-thin triangles with angles close to 0° and 180°, the kind that make terrain meshes look jagged and finite-element simulations blow up numerically.

Among all those choices, one triangulation stands out. Named after the Russian mathematician Boris Delaunay, who described it in 1934, the Delaunay triangulation obeys a single elegant local rule: draw the circle that passes through the three corners of every triangle (its circumcircle), and make sure no other point of the set ever falls inside it.

That one condition — empty circumcircles, everywhere — is enough to single out a triangulation that is, in a precise sense, the "roundest" one possible. It avoids skinny triangles automatically, without ever mentioning angles at all.

Click anywhere to add a point. As soon as there are enough points, the demo triangulates them and shows every triangle's circumcircle. Any edge shared by two triangles whose circumcircle contains the opposite corner is illegal — flipping it (swapping the shared diagonal of the resulting quadrilateral) removes the violation.

<p class="hint">{{hint_para}}</p>
<svg id="canvas" class="canvas" viewBox="0 0 500 320" xmlns="http://www.w3.org/2000/svg"></svg>
<div class="status" id="status">{{status_start}}</div>
<div class="btns">
  <button id="sample" type="button">{{btn_sample}}</button>
  <button id="scramble" type="button">{{btn_scramble}}</button>
  <button id="flip" type="button">{{btn_flip}}</button>
  <button id="autofix" type="button">{{btn_autofix}}</button>
  <button id="circles" type="button" class="ghost">{{btn_circles}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.canvas { width: 100%; max-width: 500px; height: auto; aspect-ratio: 500 / 320; background: #f4f6f8;
          border: 1px solid #cdd9e3; border-radius: 8px; cursor: crosshair; touch-action: manipulation; }
.edge { stroke: #1d3557; stroke-width: 1.6; }
.edge.illegal { stroke: #e63946; stroke-width: 2.2; }
.circ { fill: none; stroke: #6d9dc5; stroke-width: 1; stroke-dasharray: 3 2; opacity: .55; }
.pt { fill: #1d3557; stroke: #fff; stroke-width: 1.4; }
.status { font-size: 1rem; font-weight: 600; margin: .55rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .42rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Press Flip illegal edges to run the classic local-improvement rule one edge at a time, or Auto-fix all to relax the whole mesh at once. Watch how a single flip can shrink a needle-thin triangle into two much rounder ones — and how the circumcircles empty out as the mesh converges to the Delaunay triangulation.

Delaunay triangulation is one of computational geometry's genuine success stories — solved, optimal, and provably so.

• The angle-maximizing property. Among all possible triangulations of a point set, the Delaunay triangulation maximizes the smallest angle that appears anywhere in the mesh. If you sort every angle from every triangulation from smallest to largest, no triangulation beats Delaunay's worst angle. This single fact is why it produces such well-shaped triangles.
• Local checks, global result. Whether an edge is legal depends only on the two triangles that share it: for a shared edge with opposite corners $p$ and $q$, the edge is legal exactly when $q$ lies outside the circumcircle of the triangle containing $p$ (and vice versa). Lawson's algorithm (1977) starts from any triangulation and repeatedly flips illegal edges — a purely local fix — until none remain, and this always terminates at the Delaunay triangulation, unique up to ties.
• Optimal running time. Building it from scratch is no harder than sorting: randomized incremental insertion and Fortune's sweep-line algorithm (1987) both run in $O(n \log n)$ time, which is optimal, since the triangulation of $n$ points contains enough information to sort them.
• The exact dual of a solved problem. Every edge of the Delaunay triangulation corresponds to two neighboring regions of the Voronoi diagram — the two structures determine each other completely. Whatever you can say about one, you can say about the other.

No NP-hardness lurks here. The interesting content is entirely in the proof that a simple local rule (empty circumcircles) forces a global optimum (max-min angle) — a small miracle of geometry, not a computational obstacle.

Avoiding skinny triangles sounds like a cosmetic concern, but it decides whether entire numerical methods succeed or fail:

• Finite-element simulation: solvers for stress, heat and fluid flow lose accuracy — sometimes catastrophically — on needle-thin elements, which is why mesh generators build on Delaunay triangulation and its angle guarantee.
• Terrain and 3D surface reconstruction: turning a cloud of elevation samples or a LIDAR scan into a realistic surface starts by Delaunay-triangulating the points, so the resulting mesh has no thin, spiky artifacts.
• Geographic and spatial analysis: because the Delaunay triangulation is the dual of the Voronoi diagram, it is a natural tool for interpolation, nearest-neighbor queries and network design over scattered geographic data.
• Computer graphics and games: procedural terrain, navigation meshes for pathfinding, and surface reconstruction from 3D scans all lean on the same empty-circumcircle idea.

Any time a real-world computation depends on well-shaped triangles from an arbitrary set of points — and the geometry problem of Closest Pair shows how much structure a plain scatter of points can hide — Delaunay triangulation is the default, dependable answer.

The Delaunay triangulation is what happens when a single local, checkable rule — keep every circumcircle empty — turns out to have an enormous global consequence: the smallest angle anywhere in the mesh is as large as it can possibly be. No search, no compromise, no NP-hardness. Just flip the illegal edges and the best-shaped triangulation falls out on its own.

It is a reminder that not every hard-sounding geometric question is intractable — sometimes the elegant answer and the efficient algorithm are exactly the same thing, running in optimal $O(n \log n)$ time and quietly holding up meshes, maps and simulations everywhere.