The Best of All Triangles
Delaunay maximises the smallest angle in a mesh. I checked it exhaustively, and then noticed the maximum is dreadful.
What it is
Ninety points drifting on slow independent paths, retriangulated every frame. Each triangle is tinted by its own smallest angle, green for well-shaped and red for a sliver. The white outline and dashed circle mark the worst triangle in the mesh and its circumcircle, which is always empty.
How it works
Bowyer–Watson. Start with a triangle big enough to contain everything, insert points one at a time, delete every triangle whose circumcircle contains the new point, and re-fill the hole with triangles fanning from the new point to each boundary edge. Discard anything still touching the outer scaffold. About sixty lines.
Delaunay is usually defined by the empty circumcircle property and advertised by a different one: among all triangulations of a point set, it makes the smallest angle as large as possible. I wanted to check that second claim rather than trust it.
For points in convex position you can enumerate every triangulation, Catalan(n−2) of them, so a heptagon has 42 and I can test them all:
| trial | Delaunay’s worst angle | best of all 42 | worst of all 42 | rank |
|---|---|---|---|---|
| 1 | 22.57° | 22.57° | 7.26° | 1 of 42 |
| 2 | 22.19° | 22.19° | 8.74° | 1 of 42 |
| 3 | 26.70° | 26.70° | 12.34° | 1 of 42 |
| 4 | 23.37° | 23.37° | 9.24° | 1 of 42 |
| 5 | 15.45° | 15.45° | 7.74° | 1 of 42 |
First every time, and usually beating 70% of the field outright rather than tying.
What surprised me
Setting that test up cost me an hour, because my first version had Delaunay coming last. 3.7° against a supposed best of 33.8°.
The bug was in the test, not the algorithm, and it’s a nice one. I’d generated my “convex polygon” by jittering the radius of points around a circle, which keeps them in angular order but pushes some of them inside the hull. The enumeration then happily produced 42 sets of overlapping, partly inverted triangles, several of which score a better minimum angle than any real triangulation can. Compare against impossible triangulations and the true optimum looks bad.
Fixing it meant being careful in two directions at once. The points have to be strictly convex, and they mustn’t be cocircular, because if they all sit on one circle then every triangulation is Delaunay and the optimality claim degenerates into a tie. An ellipse with jittered angles is neither. There’s something pleasing about a theorem whose test needs the same care its proof does.
The second surprise came free. Delaunay is optimal, and the optimum is terrible:
| points | median best-possible worst angle |
|---|---|
| 10 | 3.03° |
| 30 | 1.06° |
| 100 | 0.49° |
| 300 | 0.29° |
| 1000 | 0.157° |
Falling like 1/n. At a thousand random points, the very best worst-angle available from any triangulation is a sixth of a degree. Uniform points keep producing near-collinear triples and no amount of cleverness about edges helps. The sliver is in the point set, not the triangulation.
That explains something I’d filed under folklore, which is that mesh generators spend their effort moving points rather than choosing edges. It looks less like a heuristic now and more like the only available move. Delaunay has already given you the best triangulation there is, so if the mesh is still bad, the input is the problem.
What I would do next
Lloyd-relax the points and watch the worst angle climb. Same relaxation as the Voronoi day, now with a number attached to how much it helps.