Voronoi — the series
-
The plane, divided by whoever is nearest
Scatter some points and colour every other point of the plane by which one is closest. The result is a tiling nobody designed, and its dual triangulation has a property that no part of the construction mentions.
-
One dimension up, and the circles disappear
The Delaunay triangulation is defined by a condition about circles, which is awkward to compute and awkward to reason about. Lift every point onto a paraboloid and the circles turn into planes, the condition turns into convexity, and a two-dimensional problem is solved by looking at a three-dimensional shape from underneath.
-
Every site in the middle of its own cell
Move each point to the centre of mass of its own Voronoi cell, then redraw the diagram, then do it again. The rule is two lines long, it never mentions hexagons, and what it settles into is a honeycomb.
-
When the sites are not the same size
Give every site a weight and the boundaries slide. The cells stay convex and the edges stay straight, which is surprising, and one thing happens that the unweighted diagram never allows — a site can end up owning nothing at all.
-
The tree inside the triangulation
The shortest network joining a set of points is built from edges chosen by length, and the triangulation is built from edges chosen by an emptiness condition about circles. The two constructions share no step, and every edge of the first is an edge of the second.
-
The skeleton inside a shape
Take the Voronoi diagram not of a handful of points but of a shape's whole outline: the points inside the shape that have two nearest points on its edge. What comes out is a skeleton — a thin branching tree that describes the shape and, with one number attached to each point, rebuilds it exactly. It is also where fires lit all round the edge would meet, and it is violently unstable: a tooth too small to notice grows a branch several times its own size.
-
A skeleton that ignores small teeth
The medial axis of a shape grows a branch to every bump on its outline, however small, so a scanned shape has a skeleton made mostly of noise. Keep only the points of the axis whose nearest boundary points are spread across a circle of radius at least λ, and the branches to bumps smaller than about 2λ disappear while the real skeleton stays. That λ-medial axis moves only a little when the outline wobbles by much less than λ — and the price is λ itself, a size below which a feature is declared not to exist, which can even cut a shape's skeleton in two.
-
The shape of a cell around a random point
Scatter points at random and give each the region nearer to it than to any other. The cells come in every shape from triangles to twelve-sided polygons, and almost nothing about them is fixed by a formula — except one thing: on a closed surface they have exactly six sides on average, every time, because three cells meet at every corner. Two hundred thousand cells measure the rest: 29.5 per cent hexagons, Lewis's law, and small cells surrounded by large ones.