The shape of a cell around a random point

Nearest neighbour divides the plane built the Voronoi diagram of a handful of chosen points, and every site in the middle of its own cell let the points move, each to the centre of its own cell, until the diagram settled into a honeycomb. This essay does neither. It scatters points independently and uniformly at random — a Poisson process, the model of points that know nothing about each other — and looks at the cells exactly as they fall. The result is the Poisson–Voronoi tessellation, the reference pattern against which every naturally occurring cellular structure, from cracked mud to biological tissue to the grains of a metal, is compared, because it is what cells look like when nothing has organised them.

Almost nothing about a Poisson–Voronoi cell is given by a formula. The share of cells with six sides, the spread of their areas, the way large cells sit beside small ones — all are known numerically, and most only numerically. One thing is exact, and it is exact for every single pattern rather than on average: the cells have six sides on average. The figures measure that exactness, then measure the rest, and find the patterns that turn out to be approximately but not exactly true.

Cells on a torus #

A random pattern on a finite square has a problem at its edges: the cells there are cut off, and their shapes are artefacts of the boundary rather than of the randomness. The figures avoid it by working on a torus — a square whose top edge is joined to its bottom and its left edge to its right, so that a point near one edge has neighbours across the other. Every cell is then a genuine cell of an infinite periodic pattern, the plane tiled by copies of the square, and no cell is special.

Each cell is computed directly from its definition. Start with a square round the cell’s point and cut it by the perpendicular bisector between that point and each nearby point, keeping the half nearer the cell’s own point; what survives all the cuts is the cell. Nearby points are found through a grid of buckets, each at its nearest copy across the joined edges, and the search radius is doubled until the cell lies within half of it — beyond that distance no bisector can reach the cell, so no point could have been missed. The number of sides is the number of bisectors that bound the final polygon, which is also the number of the cell’s neighbours. Every pattern was checked for one global property: the cells’ areas add to exactly the area of the torus, to within $10^{-9}$, so nothing is double-counted or missed.

What a Poisson process is #

The points are placed by the simplest rule that is still interesting: each point uniformly in the square, independently of all the others. On a large region that makes the number of points in any sub-region a Poisson count, with mean proportional to its area, and the counts in regions that do not overlap independent of each other — the same Poisson law that how many get their own hat found counting fixed points of a random permutation, here counting points in a patch of plane. Nothing about the pattern prefers any distance or direction, and that is what makes it the null hypothesis for spatial patterns: a set of trees, nests or stars that departs from it has been arranged by something.

Two of the pattern’s properties can be computed in one line, and both bear on the cells. The chance that a disc of radius $r$ round a point contains no other point is $e^{-\lambda\pi r^2}$ for points of density $\lambda$, so the distance to the nearest neighbour has mean $1/(2\sqrt\lambda)$ and a long tail. And a cell’s corners are the centres of empty circles through three points, the circumcircles of the Delaunay triangles that nearest neighbour divides the plane found dual to the Voronoi diagram, whose emptiness is exactly what makes them corners. The randomness of the cells is the randomness of those empty circles: a cell is small when its point is crowded, large when its point sits in a gap, and its number of sides counts how many of the surrounding points are close enough to share a corner with it.

Six, exactly #

In the hero figure, 167 of the 600 cells are hexagons — fewer than a third — and the rest range from triangles to nine-sided cells. Yet the total number of sides, added over all 600 cells, is 3,600, exactly six times the number of cells.

That is not a coincidence of the sample but a consequence of two facts. First, at every corner of a Voronoi tessellation of points in general position exactly three cells meet, since a corner is a point equidistant from three of the points and a fourth would need a coincidence of probability nought. So every corner has three edges, every edge two corners, and the number of corners $V$ is two thirds of the number of edges $E$. Second, Euler’s formula, which every corner pays for itself derived for solids, holds on a torus in the form $V - E + F = 0$. Substituting $V = 2E/3$ gives $E = 3F$, and since every edge is a side of two cells, the sides add to $2E = 6F$. The figure confirms it for patterns of every size: 300 sides for 50 cells, 120,000 for 20,000 cells, without exception.

Twelve pentagons whatever the hexagons found the same argument on a sphere, where Euler’s formula has 2 instead of 0 and forces a fixed total of twelve units of deficit in any tiling by three-cornered cells. On the torus the deficit is nought, so the cells’ departures from six must cancel exactly: every pentagon is paid for by a heptagon, every triangle by three extra sides elsewhere. That is the whole of what geometry imposes on the counts. Everything else in the next figures is a property of randomness.

How many sides #

The average is fixed; the distribution is not, and the next figure measures it over ten independent patterns of twenty thousand points each.

The shares are $0.011$ for triangles, $0.106$ for quadrilaterals, $0.260$ for pentagons, $0.295$ for hexagons, $0.200$ for heptagons, $0.090$ for octagons, $0.029$ for nine sides, $0.007$ for ten, and smaller still beyond, with a single twelve-sided cell in about four thousand. The distribution is lopsided: there are more cells with five sides or fewer than with seven or more, and the shortfall in numbers is made up by the larger cells having more sides each. Its variance, the mean of $(n - 6)^2$, is $1.77$, close to the value $1.781$ computed by numerical integration in the literature. The spread is wide enough that the commonest shape is far from typical: a cell chosen at random is more likely not to be a hexagon than to be one by more than two to one, and nearly a quarter of cells have four sides or fewer or eight or more. A tiling in which most cells were hexagons, as in a honeycomb or a well-aged foam, would have a variance far below one.

None of these shares has a closed form except one. Pierre Calka computed in 2003 the exact probability that a Poisson–Voronoi cell is a triangle, as an explicit integral whose value is about $0.0112$ — the figure’s $0.0111$ agrees to its sampling error — and no comparable result is known for any other number of sides. The hexagon share, the most quoted number about random cells, is known to three or four decimal places from simulations like this one and from numerical evaluation of multiple integrals, and not from a formula.

Lewis’s law #

Cells with more sides are larger. The next figure measures by how much.

Triangles average a third of a typical cell’s area, quadrilaterals $0.56$, pentagons $0.77$, hexagons almost exactly one, heptagons $1.22$, octagons $1.45$, and so on up to $2.15$ for eleven-sided cells. The increase is close to a constant $0.22$ to $0.24$ per side, so the average area is nearly a straight line in the number of sides. Frederic Lewis noticed exactly this in 1928, counting the cells in the skin of a cucumber, and it has been found since in many plant and animal tissues, in soap froths and in metal grains. For the random tessellation it is approximate: the steps are not quite equal, and the line bends slightly at both ends. A tissue that obeys Lewis’s law much more exactly than the random pattern, or with a different slope, is telling something about the forces that shaped it, which is why biologists measure it.

The areas themselves are spread with variance $0.278$ about their mean, which is exactly one in units of the average cell since the cells tile the torus. Edgar Gilbert expressed that variance as an integral in 1962 and evaluated it numerically as about $0.280$, and the figure agrees. The distribution of areas is skewed to the right, with no cell of area nought and a long tail of large cells, and it is well described, though not exactly, by a gamma distribution.

Small cells among large ones #

A cell’s neighbours are not a random sample of cells. The next figure measures how their sides depend on the cell’s own.

The neighbours of a triangle average $7.01$ sides; of a hexagon, $6.32$; of a ten-sided cell, $5.87$. Small cells are surrounded by large ones and large cells by small ones. The relation is approximately linear when written as $n \cdot m(n)$, the total number of sides of a cell’s neighbours: the points lie close to $n\,m(n) = 5.30\,n + 5.75$. David Aboav found such a linear relation in the grains of polycrystalline magnesium oxide in 1970, and Denis Weaire derived it approximately, which is why it is called the Aboav–Weaire law. For the random tessellation the points bend gently away from any line, so the law is an approximation here too; for a few structures it is exact, and for some biological tissues it holds with constants quite different from these.

One average is fixed exactly, by counting each side twice. The average over all cells of $n\,m(n)$, weighted by the share of cells with each $n$, is the average over all edges of the product of the sides of the two cells it separates, and that equals 36 plus the variance of the number of sides — about $37.77$ with the variance measured above. The Aboav–Weaire line, whatever its slope, has to be consistent with that identity, which is why its two constants cannot be chosen independently.

Mud, foam and tissue #

The reason these numbers are tabulated is comparison. A cellular structure in nature — the polygons of dried mud, the bubbles of a foam, the cells of an epithelium, the grains of a cooled metal — can be measured in the same way, and its side distribution, area spread and neighbour relations set beside the random pattern’s. The departures are informative. A foam that has coarsened for a long time has relaxed towards three-fold corners at equal angles, and its share of hexagons is well above the random pattern’s 29.5 per cent; in many plant and animal epithelia the share of hexagons is around 45 per cent, with pentagons and heptagons making up most of the rest and squares and octagons rarer than in the random pattern; cracked mud, which breaks at T-junctions rather than three-fold symmetric ones, has more four-sided cells than any Voronoi pattern.

What a comparison can establish is limited, and the random pattern helps say how. Two quite different processes can produce the same side distribution, and the side distribution of a tissue says little on its own about the forces in it. But the variance of the number of sides is a robust single measure of disorder, nought for a honeycomb and $1.77$ for random points, and real structures fall between, ordered by how much their growth has organised them. The weighted Voronoi diagrams of when the sites are not the same size give another family of reference patterns, with cells whose sizes are set by weights rather than by chance, and between those and the random pattern lies most of what is observed.

What the measurements cannot show #

The figures are samples, two hundred thousand cells in ten patterns, and the shares, the variance and the fitted line carry sampling errors of a few in the fourth decimal place. They agree with the published numerical values to that accuracy, which is evidence that the computation is right; they do not determine any of the constants better than the literature already does. The exact statement in the figures is the average of six, which needs no sample at all.

The torus is a convenience whose cost is periodicity. A pattern of twenty thousand points on a torus is an infinite pattern that repeats every square, and correlations longer than the square are cut off; for cells of typical size a hundredth of the square’s side, that matters for nothing measured here, but it would matter for questions about very long-range structure. The figures also show only two dimensions. In three, where one dimension up the circles disappear into spheres and the cells become polyhedra, the cells have about $15.5$ faces on average, and that average is not exact: Euler’s formula in three dimensions does not fix it, and its value, $48\pi^2/35 + 2 \approx 15.54$, comes from an integral computed by Meijering in 1953.

Still open: a formula for the hexagons #

The probability that a Poisson–Voronoi cell has $n$ sides is, for every $n$, a definite number given by a multiple integral over the positions of the cell’s neighbours, and only for $n = 3$ has the integral been evaluated in closed form. The asymptotic behaviour for large $n$ is known — Hilhorst and Calka showed the share of $n$-sided cells falls roughly like $(8\pi^2)^n/(4\pi^2 (2n)!)$, with corrections, which is why twelve-sided cells are already so rare — and the value for six sides, $0.2945\ldots$, has been pinned down to several decimal places by evaluating the integral numerically, but no formula is known or expected to be simple.

There is also the question of what the random tessellation is the reference for. The least wall for equal rooms proved that the honeycomb is the best way to divide the plane into equal areas, and Lloyd’s iteration drove random points towards it. Between the random pattern and the honeycomb lies every real cellular structure, and quantities like the variance of the number of sides — $1.77$ here, nought for the honeycomb — are used to place them on that scale. Which measurements of a tessellation determine how it was made is a question for each application, and the random pattern’s role is to say what nothing-in-particular looks like.

Exactly six, and nothing else exact #

The cells of a random pattern are as irregular as cells can be: triangles beside twelve-sided polygons, areas spread with variance $0.28$, neighbours anticorrelated in size. Out of all that irregularity one number is fixed for every pattern, the average of six sides, and it is fixed by topology rather than by probability — three cells at every corner and Euler’s formula on the torus leave no freedom. The other regularities, Lewis’s near-linear areas and Aboav and Weaire’s near-linear neighbours, hold approximately and are constrained by the exact one. The tree inside the triangulation found a hidden structure in the dual of a Voronoi diagram for any point set; for random points the hidden structure is simpler and more surprising — an exact average that no individual cell needs to respect, and that the whole pattern respects without fail.