A cell's children do not fit inside it

Ten rungs of this ladder price a cell system at one resolution: its shape, its area, its address, its neighbours, the query it answers, the statistic it reports.

Every one of those systems is used hierarchically. A cell has a parent and children, a statistic is rolled up the tree, a query descends it, an index is a path through it. And the rolling up rests on something nobody states, because on the systems most people grew up with it costs nothing.

The assumption #

A parent is the union of its children. That is what makes a roll-up a roll-up: the sum over the children is the total over the parent, because the children partition it.

On a square grid it is exactly true, and on a latitude–longitude grid it is exactly true, which is why every pyramid, every quadtree and every tile scheme in a screen map is a pyramid of tiles can be reasoned about without ever mentioning it.

On a hexagonal hierarchy it is false, and it is false by construction rather than by approximation.

Why it cannot be arranged #

The obstruction is elementary and it is worth stating before any number, because it explains why no clever choice of ratio fixes it.

A hexagon cannot be tiled by smaller hexagons at any ratio whatsoever. Hexagons tile the plane, so a hexagonal lattice exists at every scale; what does not exist is a way to fill one hexagon with a whole number of smaller ones. That is the same class of fact as hexagons cannot tile the sphere, one rung down, arriving in the plane rather than on the sphere and for a different reason.

What a hexagonal system does instead is aperture: the parent lattice is a sublattice of the child lattice, chosen so that each parent’s Voronoi cell contains a fixed number of child centres — three, four or seven, depending on the scheme. The children assigned to a parent are the ones whose centres lie in it, and their count is right.

Their area is right too, exactly: seven children at one seventh of the parent’s area is the parent’s area. What is wrong is where that area sits.

A lattice’s Voronoi cell inherits the lattice’s orientation, and the aperture-seven sublattice is generated by a vector at

$$\arctan\frac{\sqrt3}{5} = 19.1066^\circ$$

to the child lattice’s own generator. So the parent hexagons are turned by 19.107° relative to the child hexagons, and two families of hexagons at an angle cut each other. There is nothing to tune.

What was computed, and how #

Everything here is planar and every number is a closed form.

The child lattice is generated by A = d(1, 0) and B = d(½, √3/2). The parent lattice for aperture seven is generated by 2A + B, whose length is d√7; for aperture three it is A + B, at d√3. A hex lattice of centre spacing s has Voronoi hexagons of circumradius s/√3, so the parent’s circumradius is √7 times the child’s and its orientation is the parent generator’s plus thirty degrees.

The children are the aperture child centres nearest the origin. Each child hexagon is clipped to the parent by Sutherland–Hodgman, and the clipped area is a shoelace. No sampling, no quadrature, no tolerance.

The answers are rationals:

Both hexagonal figures are checkable by hand from the fractions in the middle column. At aperture seven, one whole child plus six at eleven twelfths is 1 + 5½ = 6½ child areas inside a parent worth 7 of them, so the coverage is 13/14 and the defect 1/14. At aperture three, one whole plus two at a third is 5/3 inside a parent worth 3, so the coverage is 5/9.

7.14 per cent at aperture seven, and 44.4 per cent at aperture three. The second number is the reason no operational system uses aperture three alone, and the first is the number every operational hexagonal system carries.

What the count is right about #

It is worth being precise about which properties survive, because a system that got them wrong would be useless rather than merely imperfect.

The count is exact. Every child centre lies in exactly one parent, so every cell has exactly one parent and the tree is a tree. Seven children per parent, at every level, with none shared and none orphaned.

The total area is exact. Seven children at one seventh of the parent’s area is the parent’s area, to the last bit — this is asserted rather than assumed, because a construction that got it wrong would produce a defect that was an arithmetic error rather than a geometric fact.

The partition is exact at each level. Every point of the plane is in exactly one cell of each resolution. What fails is only the relation between two levels.

So the failure is narrow and specific: the tree is a valid tree whose nodes do not contain their descendants. That is a strange object and it is the one every hexagonal global grid is.

It does not go away with resolution #

The defect is a ratio of areas of similar figures, so it is scale-free: exactly the same number at every level of the tree, from a continent to a doorstep. Computed at four scales spanning four orders of magnitude, the four figures agree to the last bit.

That is what makes it a property of the hierarchy rather than an artefact. Refining a hexagonal system does not reduce it; it produces more parents, each missing one fourteenth of itself.

Where the missing fourteenth actually is #

The defect is a fraction of a parent that no child of that parent covers, and it is worth saying what does cover it, because the answer is what keeps the arithmetic honest at each level.

Every point of the plane is in exactly one child, so the missing region is covered by children of the six neighbouring parents. By the symmetry of the construction each neighbour contributes the same amount, so each of the six donates exactly 1/84 of a parent’s area across the boundary — and receives 1/84 back, in the other direction, from the parent it took it from. The books balance at every level because each parent gives away exactly what it takes in; the defect is a permutation of ground between parents rather than a loss of any.

That is also where the thirteen comes from. A parent meets its own seven children and the nearest six belonging to its neighbours, so an exact overlap matrix has thirteen non-zero entries per parent rather than seven — six of them worth 1/84 each and the other seven worth what the middle column of the table says. The repair costs not quite twice the storage of the tree it replaces, which is cheap; what it costs is the tree.

The aperture-three case is the same arithmetic run at a worse angle. A parent is worth three child areas, its own children contribute one whole plus two thirds of a child twice — five thirds — and the remaining four thirds of a child area, which is four ninths of the parent, arrives from outside. More of an aperture-three parent is furnished by its neighbours than by its own children. That is not a scheme with a larger error than aperture seven; it is a different object, and calling the cells it contains its children is close to arbitrary.

The scale-free property has a consequence worth stating too. Because the defect is a ratio of similar figures, a roll-up through k levels does not compound it into anything: each level’s misassignment is the same 7.14 per cent of that level’s parents, and the ground a cell loses at one level it does not lose again at the next. What compounds is not the area but the identity — a piece of ground can be attributed to a different lineage at every level of the tree, so two aggregations that stop at different resolutions disagree about which region a place belongs to even though neither has lost any of it.

What it costs, which is less than it looks #

Here is the part that explains why nobody has noticed.

The parent and the union of its children have exactly the same area, by construction, and exactly the same centroid, by symmetry. So the integral of any linear field over the two regions is identical: an integral of a linear function is the area times the value at the centroid, and both factors agree.

The defect is invisible to every statistic that depends on the area and the mean position alone. A count of a uniformly distributed quantity rolls up exactly. A total population over a locally linear density rolls up exactly. A centroid rolls up exactly.

It first appears in the second moments. The seven children carry 2.449 per cent more second moment about the centre than their parent does, and that ratio is the whole of the error: on a stated field with curvature 1 the rolled-up total is out by 1.207 per cent, and at aperture three by 27.5 per cent.

So the honest summary is that a hexagonal hierarchy is exact for the statistics it is usually used for and wrong for the ones with curvature in them — a variance, a spatial autocorrelation, a gradient, a second difference. Which are, unhelpfully, the statistics somebody reaches for when the first-order picture has stopped being interesting.

Where the model stops #

This is the plane. A real hexagonal global grid lives on an icosahedron projected to the sphere, so it carries the face maps of the globe on a solid and the seams of a polyhedral construction on top of everything above. Those add their own error, and separating the two is exactly why the measurement here is planar: the defect is a lattice fact, and it would be invisible inside a spherical measurement that also contained a projection.

The children are the nearest centres. A scheme is free to assign children differently — by index rather than by geometry — and some do. That changes which cells are called children and not the geometry: a hexagon still cannot be filled with hexagons, so some assignment somewhere still cuts.

And the statistic is an integral. A cell system usually holds counts of discrete things rather than integrals of a field, and a count is assigned to whichever cell contains the point. The arithmetic is the same with the field read as a density, and the discreteness adds a sampling error that has nothing to do with this one.

Why anybody uses hexagons anyway #

Stating the cost without the benefit would be a misreading, and this collection has priced the benefit already.

A hexagonal cell has six neighbours all at the same distance, where a square cell has four at one distance and four at another — which is why a cell system trades area for shape and why anything involving adjacency, diffusion or nearest-neighbour behaviour is better behaved on hexagons. A hexagon is also the most nearly circular shape that tiles, so a query is a disc, and a disc is not a cell costs less on it.

The trade is a real one and it is forced. Squares nest exactly and have unequal neighbours; hexagons have equal neighbours and do not nest. There is no tiling of the plane with both properties, because nesting requires a shape that tiles itself and the only such shapes are the ones with four-fold or triangular symmetry.

The repair, and why it is not usually made #

There is an exact way to roll up on a hexagonal hierarchy and it is the one rebinning already describes: compute the overlap of every child with every parent, and weight. The overlap matrix is small — each parent meets thirteen children rather than seven — it is the same at every level because the defect is scale-free, and it can be computed once and stored.

What that buys is exactness for the second moments as well as the first, at the cost of the property the whole hierarchy exists for: a child then contributes to more than one parent, so the roll-up is no longer a tree traversal and an index that was a path is no longer a path.

That is the trade in one line. A hexagonal hierarchy is a tree if the sum over children is taken as the parent’s value, and it is exact if it is not a tree. Every operational system takes the first, which is the right call for the statistics they carry and is a choice that nothing in their documentation records having made.

The generalisation #

A property that holds exactly at one level of a structure is not a property of the structure. A hexagonal grid is a partition of the plane at every single resolution, and no two of those partitions refine each other.

The collection has met this shape before with a different object. A chain of transformations does not close is the same statement about datum shifts: each one is right, and the composition is not the one a direct transformation would give. Simplification does not commute with the projection is the same statement about two operations. Here the two things that fail to agree are one system at two resolutions, which is the least suspicious pairing of the three — the same scheme, the same code, the same cells, one level apart.

That is what makes it worth a rung. The failure is between an object and itself. Two datums are two conventions and can be expected to disagree; two operations are two orderings and can be expected not to commute. One scheme at two of its own resolutions is the case where nobody thinks to look, because there is only one thing there.

One number is worth stating in the units a practitioner uses. A defect of one fourteenth is 7.14 per cent of a parent’s area, and on a system whose cells are a kilometre across that is seventy-one thousand square metres of ground per parent that no child of that parent covers. It is covered — by a child of a neighbouring parent — so nothing is lost and nothing is double-counted at any single level. What is wrong is only which parent it is counted under.

Who found it, and when #

Hexagonal discrete global grids date from Sadourny’s work in the 1960s and the systematic treatment from Sahr and White in the 1990s and 2000s, which is where the aperture vocabulary comes from. That literature is explicit that hexagonal apertures are not congruent refinements — the term of art is that hexagons are not hierarchically nesting, and the aperture-7 rotation is standard.

What the treatments do not usually carry is the number. The defect is a rational and it is not hard to compute, but it appears in practice as a caution rather than as one fourteenth, and the distinction between the children do not tile the parent and the roll-up of a linear statistic is nevertheless exact is the part that decides whether it matters for a given use.

Both halves are needed to use the system honestly, and they point opposite ways. A practitioner told only the first would avoid hexagons for work where they are exactly correct; one told only the second would trust them for a variance.

Where the ladder goes next #

Eleven rungs price a cell as a shape, as an address, as a query target and now as a member of a family. What none of them prices is a cell as a thing that changes — a system that is re-defined, re-indexed or re-projected between two releases, so that a cell with the same address is a different piece of ground. That is a version problem rather than a geometry one, and it is the failure a stored coordinate is least protected against.