Starting points
What a Voronoi diagram is
Put some points on a plane. Every other position on that plane belongs to whichever point is nearest. That is the whole definition, and the partition it produces is a Voronoi diagram. There is nothing else to specify — no parameters, no fitting, no choices — which is why the same shape turns up in mobile-phone cell coverage, giraffe markings, foam, crystal grains, catchment areas for railway stations, and the way a forest canopy divides light.
Because the boundary between two cells is the set of points equidistant from both, every edge is a segment of a perpendicular bisector, and every cell is an intersection of half-planes — so cells are always convex polygons under Euclidean distance. Change the distance and that stops being true: switch to Manhattan and the boundaries pick up staircase corners, because “equally far” now means equally far by city blocks.
Lloyd relaxation, and why it makes hexagons
Press Relax ×40. Each step moves every point to the centre of mass of its own cell and recomputes the diagram. Repeat and randomly scattered points drift into something that looks like a honeycomb.
Measuring 400 random points through 40 iterations of this, the coefficient of variation of cell area drops from 0.540 to 0.108 — the cells become five times more uniform in size — and the proportion of cells with exactly six sides rises from 31.4% to 69.2%. The readout above measures the CV the same way, on a grid of about 900 cells per point, so you can watch it fall. One run is one sample, though: over eight different random scatters of 400 points, 40 steps ended anywhere from 0.08 to 0.17, averaging 0.12. A single press of Relax ×40 will land somewhere in that range, not on 0.108 exactly.
Six is not a coincidence, and it is also a ceiling. For any planar subdivision, Euler’s formula forces the average number of edges per cell to stay below six, approaching it only as the number of cells grows. Relaxation cannot push the average past that; all it can do is concentrate the distribution onto the mean. So the honeycomb is not the algorithm imitating bees — it is the only arrangement left once you have made the cells equal and the topology has no room for anything else.
The full measurement, including what happens under non-Euclidean distances, is written up in Japanese here.
Uses for the relaxed version
Points that have been through a few rounds of Lloyd relaxation are approximately blue noise: random-looking but with no clumps and no gaps. That property is worth a lot in rendering — it is what stops sampling patterns from producing visible artefacts — and it is also what makes relaxed Voronoi cells the standard starting point for stippling, procedural terrain regions, and shattering effects.
How this page draws it
There is no polygon construction here. The points are uploaded to the GPU as a texture, and for every pixel the fragment shader simply finds the nearest and second-nearest point. The colour comes from the nearest one; a border is drawn wherever the two distances are nearly equal. That brute-force approach is asymptotically far worse than Fortune’s sweepline algorithm, and far faster in practice at these sizes, because the GPU is doing a few hundred million independent comparisons per frame and does not care.