A cell system trades area for shape

Two rungs have established what a cell scheme is asked for: equal areas, so that a count per cell is a density, and compact shapes, so that a neighbourhood query fetches few cells. The obvious question is whether a scheme can have both.

It cannot, and unlike the twelve pentagons this is not a theorem — it is a measurement, made on four schemes with the same code and the same two criteria.

The four schemes #

The lon/lat quadtree, from the first rung: boundaries along the graticule, areas varying by a factor that doubles with every level.

The raw cube. Six square faces of a cube inscribed about the sphere, each divided into a quadtree, each cell projected outward from the centre. That is the inverse gnomonic, so the cells near a face’s centre are smaller on the sphere than the ones at its corners.

The tangent-warped cube. The same, with each coordinate passed through u ↦ tan(uπ/4) before projecting. The warp is the one Google’s S2 library uses, and it exists to undo most of the gnomonic’s stretch.

The equal-area cube. The same six faces, with the area-preserving face map from what a face can preserve instead of the gnomonic — inverted, so that a uniform grid on the flat square becomes a grid of exactly equal spherical cells.

That last one is worth pausing on as a piece of construction. The polyhedral ladder built an area-preserving map from a spherical face onto a flat one by integrating an ordinary differential equation; inverting it costs a bisection on a monotone function and a closed form for the radius. The cell scheme is then free: a uniform grid on the flat face has cells of exactly equal plane area, so their images have exactly equal spherical area.

What the measurements say #

Every area below is computed with the spherical polygon formula applied to the cell’s own boundary, not derived from the construction — the point of an equal-area scheme is that the measurement comes out constant, and asserting it from the construction would be the construction repeated.

At level 2, which is 96 cells for the cube schemes:

and at level 3, 384 cells:

Three things are readable there and all three matter.

The warp works. The raw cube’s area spread is 2.48 and the tangent one’s is 1.20, for a shape cost of nothing — the tangent scheme is better than the raw one on both criteria. That is not a trade-off, it is a strictly better construction, and it is why S2 warps.

The equal-area scheme is exactly equal-area. Its 1.003 is not a residual of the construction but of the measurement, which approximates each curved cell boundary by a polygon: refining that sampling drives the spread toward one as the square of the step, fitted here at −2.01. The construction is exact and the number that is printed is a measurement of a drawing.

And it pays in shape. Its worst aspect is 1.289 against the tangent scheme’s 1.189 at level 2, and 1.394 against 1.291 at level 3. The gap is not enormous and it is systematic: forcing the areas to agree makes the cells that would have been small into cells that are the right size and the wrong shape.

The trade also has an exchange rate, and it is worth reading off the two tables because it is not what the plot’s shape suggests. Going from the tangent-warped scheme to the equal-area one buys 0.199 of area spread at level 2 — 1.202 down to 1.003 — for 0.100 of worst aspect ratio, 1.189 up to 1.289. At level 3 the same move buys 0.278 and costs 0.103. The cost in shape is essentially constant across the two levels and the purchase in area grows, so the equal-area scheme’s case gets stronger as the grid is refined, and a comparison made at a coarse level understates it.

That is the opposite of how the raw cube behaves and for a related reason. The tangent warp is an approximate inverse of one particular projection, so what it fails to cancel is a residual that grows as the grid reaches further into the face corners where the gnomonic’s stretch is worst. The equal-area construction is not an approximation of anything: it inverts an exact map, so its area spread is one at every level and only its shapes are left to degrade. A scheme whose defect is an approximation error and a scheme whose defect is a geometric fact behave differently under refinement, and the tables show it as one column moving and the other standing still.

The raw cube’s failure, read off the projection it is #

The raw cube scheme is worse than the other two at everything, and it is worth saying exactly why, because the reason is a projection this site has already measured.

Laying a uniform grid on a face and projecting outward from the centre of the sphere is the gnomonic projection, inverted. The globe on a solid measures what the gnomonic does across a cube face: the areal factor runs from 1.00 at the face’s centre to 4.46 at its corners. So a uniform grid on the flat face becomes a grid whose spherical cells are largest at the face centre and smallest at the corners, by very nearly that factor.

The warp is therefore not a fudge but a partial inverse: tan(uπ/4) is chosen so that equal steps in u become nearly equal steps of arc, which is exactly what undoing a gnomonic requires. It gets the spread from 3.79 to 1.28 with one elementary function, and what is left is the residual of an approximation rather than of a construction.

The lon/lat scheme is not on the same scale as the others #

The fourth row of the tables is off the chart, and the reason is worth repeating in this company.

At level 3 the lon/lat scheme’s area spread is 5.03 and its worst aspect ratio is 5.13, against a cube scheme’s 1.28 and 1.29. It is worse on both criteria by a factor of four, and — the part that matters — its numbers grow with the level while the cube schemes’ do not grow the same way: 10.15 at level 4, 40.74 at level 6, 162.97 at level 8.

The comparison is not close and it is not a matter of taste. Any of the three cube schemes dominates the graticule-based one at every level and on both criteria, which is why no serious global grid is built on the graticule and why the schemes people actually use — S2, H3, DGGRID’s family — are all built on a solid.

The measurement that had to be checked before any of this could be believed #

An equal-area claim measured by a method with its own bias is worth nothing, and the bias here is easy to see once looked for.

A cell’s boundary is a straight line in the face’s plane and a curve on the sphere. Measuring the cell’s area from a polygon through a finite number of points along each edge under-reports it, by an amount that depends on how curved that edge is — so the measurement systematically favours some cells over others and could manufacture a spread out of an exactly equal-area scheme.

Two checks separate the scheme from the measurement:

• The total is exactly 4π at every sampling density. Every edge is shared by two cells and the two errors are equal and opposite, so the sum is unaffected. That means the total could never have caught this problem, and it is the check most people would run.
• The spread converges as the square of the step. Measured at 4, 8, 16 and 32 samples per edge, the excess falls 0.11, 0.028, 0.0069, 0.0017 — a fitted exponent of −2.01, which is the signature of a polygon approximating a curve and not of a scheme with unequal cells.

The site’s habit of measuring convergence rather than accepting a number is what makes the difference between “the areas agree to a part in a thousand” and “the areas are equal, and here is why the number is not zero”.

Why the trade-off is the same one the whole site is about #

Nothing above proves that no scheme can have both, and it is worth being careful about that. What has been measured is that three schemes on the same solid sit at three points of a trade, and that the one which fixes area has the worst shapes.

The reason to expect it in general is the same two-line argument the trade-off is two lines makes about projections. A cell scheme is a projection of the sphere onto a set of flat faces, plus a grid on those faces. Holding every cell’s area exactly fixes the areal factor at one everywhere, which is an equal-area map; holding every cell’s shape exactly would fix the two principal scales equal everywhere, which is a conformal map; and a map that is both is an isometry, which the curvature forbids.

So the corner of the plot is empty for the same reason the corner of every plot on this site is empty, and the finite gap between the schemes is a measurement of how much of the impossibility each one has chosen to absorb.

What the numbers do as the grid is refined #

A comparison at one level is a comparison at one level, and the schemes do not all behave the same way as the cells get smaller.

The equal-area scheme’s area spread stays at exactly one by construction, at every level, forever. Its worst aspect ratio grows slowly — 1.289 at level 2, 1.394 at level 3 — because the cells near a face’s corner are the ones being stretched and they stay in the same relative position as the grid refines.

The tangent-warped scheme’s area spread grows: 1.20 at level 2, 1.28 at level 3. That is a small growth and it is a growth, and it means the scheme’s quality claim has a level attached to it.

The raw cube’s grows fastest — 2.48 to 3.79 — for the same reason the globe on a solid gives: the gnomonic’s areal factor keeps rising toward the face corners, so refining the grid puts more cells in the region where the stretch is worst.

The lon/lat scheme’s grows without bound, doubling with every level, which is the finding of the first rung.

The ordering by growth rate is therefore not the ordering by value at any single level, and a scheme chosen on a level-2 comparison and deployed at level 12 is a scheme chosen on the wrong number. That is the same trap distortion over a region sets for projections: a quantity measured over one region, or at one resolution, is not a property of the thing.

What to choose, if the question has to be answered #

The site refuses to name a best projection without an objective, and the same refusal applies here with the same structure. The objective is set by the operation, which the first rung listed:

• Aggregating counts into densities needs equal area and tolerates elongated cells, so the equal-area cube is the right answer and the shape cost is one that shows up only in query performance.
• Neighbourhood and proximity queries need compact cells and tolerate area variation, so the tangent-warped cube or a hexagonal grid is right.
• Joining datasets needs neither, and the correct choice is whichever scheme the other dataset used — a point too obvious to be worth measuring and the one that decides most real cases.

That is the same conclusion the operation decides the coordinate system reaches for coordinates, arriving at the level of the index rather than the level of the number.

Where the model stops #

Only cube-based schemes are measured on the exact trade-off. The hexagonal grids are measured on their own terms in the previous rung and are not on the same axes, because their cells are not quadrilaterals and the aspect ratio of a hexagon is a different quantity from the aspect ratio of a near-square.

The cells are quadrilaterals with curved edges, and every area here is measured from a polygon through points along those edges. That approximation is what the convergence check above is about, and it is the same class of decision densification forces on any stored boundary: a curve represented by points is a curve with a tolerance attached, and the tolerance has to be stated before any area computed from it means anything.

Aspect ratio is one shape measure among several. The perimeter-to-area ratio would rank the schemes similarly and not identically, and a query engine cares about the number of cells a disc intersects, which is a third quantity. Nothing here is a claim about which shape measure a real system should use.

The level-3 numbers do not extrapolate indefinitely. The raw cube’s area spread grows with the level — 2.48 at level 2, 3.79 at level 3 — because the extremes move toward the face corners, while the tangent scheme’s and the equal-area scheme’s do not grow the same way. Comparing schemes at one level is comparing them at one level.

The hierarchy is what none of this touches #

Every quantity in this essay is metric — an area, a shape, a ratio — and every one of them is fought over. The property that makes a cell scheme useful, though, is not metric at all, and it is the same on all four.

A cell’s children partition it exactly. The four cells one level down whose identifiers extend a cell’s identifier by one step cover precisely that cell and nothing else, whatever the warp. That is what lets an index be walked, a query prune a subtree, and two datasets at different levels be joined by prefix.

Containment survives every projection because a projection is continuous and one-to-one on a face, and containment is a statement about which sets are inside which. So the trade-off measured here is entirely inside the metric half of the problem, and the half that matters most for a database is untouched by it — which is worth stating, because a reader who has just been shown four schemes disagreeing might conclude the choice is fraught. It is fraught for aggregation and irrelevant for indexing, and knowing which is which is most of the decision.

Who found it, and when #

The tangent warp is folklore in the graphics literature and was in use in the “quadrilateralised spherical cube” that NASA’s COBE mission used for its all-sky maps in the early 1990s — a scheme designed for exactly the reason this ladder is about, since a map of the microwave background is a count per cell and needs equal areas.

The exact equal-area map of a square onto a sphere face has been derived several times: Snyder’s polyhedral projection of 1992 gives it for any regular solid, and Roşca and Plonka published an explicit area-preserving cube map in 2011. The version used here is the first of those, inverted.

What appears to be genuinely uncommon is the comparison: three schemes on the same solid, measured on the same two criteria with the same code, so that the trade between them is a pair of numbers rather than an argument about which library to use.

Where the ladder goes next #

The cells anchor now has an address, an obstruction and a trade-off. What it does not have is the question a working system asks next: how many cells does a query touch? That is a measurement about discs and boundaries rather than about single cells, it depends on the scheme’s shapes in a way the aspect ratio only approximates, and it is work this collection has not done.