VORONOI & DELAUNAY LAB
Two pictures of the same thing. The Voronoi diagram answers “which point is nearest”; the Delaunay triangulation is its dual, and it is the triangulation that avoids thin slivers — which is why mesh generators want it.
Click to add a site, drag one to move it, shift-click to remove it. Relax runs Lloyd's algorithm: every site jumps to the centre of its own cell. Repeat it and a random scatter turns into a honeycomb, because the hexagon is what a Voronoi cell wants to be.
The triangulation is built by Bowyer–Watson insertion: add a point, delete every triangle whose circumcircle contains it, and fill the hole that leaves. The defining property is that no site ends up inside any triangle's circumcircle — turn on Circumcircles and you can watch it hold. The page checks it after every change, along with Euler's formula for a planar graph, and says so above.
Cells are built as an intersection of half-planes: start with the rectangle, then cut with the perpendicular bisector between the site and each of its Delaunay neighbours. Cutting against neighbours alone is enough — a Voronoi edge only ever separates Delaunay neighbours — and the page verifies that shortcut against the brute-force version, which cuts against every other site, whenever there are few enough sites to do it live.
"Every cell is the set of places closer to its own site than to any other. That one sentence is the whole diagram."