An address is an area

A latitude and a longitude name a point. A cell identifier — a geohash, an S2 token, an H3 index, or the row and column of any grid at all — names a region, and the difference is not a technicality about representation. It changes what the number can be asked.

Two coordinates can be subtracted to give a distance. Two cell identifiers cannot: what they support is joining, counting and indexing, and the quantity that decides how well they support it is the area of a cell.

The precision of an identifier is an area, and it is computable #

The obvious global grid divides the world by halving in latitude and longitude: level L gives 2^L rows and 2^(L+1) columns, and the identifier is the path down the tree.

Each level quarters the cell, so the area falls by a factor of four per level exactly. That is a property of the scheme rather than of the Earth, and it is what makes an identifier length translate into a ground area at all:

Every one of those areas is a closed form — R²·Δλ·(sin φ₂ − sin φ₁) — with no dataset behind it and no error bar attached, for the same reason computing an area needs a surface gives for using cells rather than coastlines throughout this site.

The same identifier length is not the same amount of ground #

The table above says equatorial, and that word is carrying the whole of this essay’s complaint.

A lon/lat cell’s area is proportional to sin φ₂ − sin φ₁, which shrinks as the cell moves north while the identifier does not change at all. Measured:

The ratio doubles with every level, without limit, because the polar row’s area falls as the square of its latitude span while an equatorial row’s falls linearly. There is no depth at which the scheme becomes uniform; it becomes less uniform the finer it is cut.

The consequence is the practical one and it is easy to state. A count of anything per cell — sightings, deliveries, measurements — is a count per unit area only if the cells have equal areas. On this scheme, at level 8, a northern cell’s count covers a hundred and sixty times less ground than an equatorial one’s, so a map of those counts is mostly a map of the grid. That is the same error thematic mapping makes when it shades a non-equal-area projection, arriving here without any projection being involved at all.

A cell is also a shape, and this one stops being square #

Area is not the only property a cell has. The other one that matters for indexing is its aspect ratio — how far from square it is — because a long thin cell has a large perimeter for its area, so a query about a neighbourhood touches more cells than it should.

On the lon/lat scheme the aspect ratio is the same 10.2 at level 4 and 163 at level 8 as the area spread, for the same reason: at high latitude the east–west extent collapses while the north–south one does not. A polar cell at level 8 is 78 kilometres tall and half a kilometre wide.

Every scheme that is used seriously abandons the lon/lat grid for exactly this. The alternatives — dividing a cube, or a subdivided icosahedron — are what the rest of this ladder measures.

What a cell scheme is actually for, and what each use demands #

Three operations account for nearly every use of a global grid, and each of them puts a different requirement on the geometry. Listing them is what turns the measurements above into criteria rather than complaints.

Joining. Two datasets are combined by matching identifiers, which needs nothing geometric at all — only that both sides used the same scheme, at the same level, on the same datum. This is the operation cells are best at and the one that makes them worth having: no arithmetic, no tolerance, no nearest-neighbour search.

Aggregating. A count or a sum per cell becomes a density only when divided by the cell’s area, and becomes comparable between cells only when the areas are equal. A scheme whose areas vary by 163 either has to carry an area per cell through every calculation or has to be equal-area by construction. That is the requirement the third rung of this ladder is about.

Neighbourhood queries. What is within five kilometres is answered by finding the cells that intersect a disc, and how many that is depends on the cell’s shape rather than its area. The arithmetic is short: a rectangle of area A and aspect ratio a has perimeter 2√A(√a + 1/√a), so against a square’s 4√A, a cell of aspect 10 has 74 per cent more boundary and one of aspect 163 has five and a half times as much. Boundary is what a neighbourhood query pays for, because every cell the disc’s edge crosses has to be fetched and filtered.

The three demands are not the same and they do not have a common optimum. Joining wants nothing; aggregating wants equal area; querying wants compact shape. A scheme is a position on that trade rather than an answer to it, which is the same shape of argument which projection is best makes about projections and for the same underlying reason.

The doubling has a closed form, and it is 2/π #

The area ratio’s doubling is measured across the level table and it is exact rather than empirical, which is worth showing because the constant in front of it turns the ratio into something predictable before a level is chosen.

At level L a row spans δ = π/2^L radians of latitude. An equatorial cell’s area is proportional to sin δ and a polar one’s to 1 − cos δ, so

$$\text{ratio} = \frac{\sin\delta}{1-\cos\delta} \;\longrightarrow\; \frac{2}{\delta} = \frac{2^{L+1}}{\pi}.$$

At level 8 that is 512/π = 163.0, against a measured 162.97. At level 6 it is 40.74 and at level 4, 10.19 — the whole column, from one expression, with the small departures at the coarse end being the small-angle approximation rather than anything about the Earth.

So the ratio is not merely growing; it is 2^(L+1)/π, and it is the reciprocal of half the polar row’s angular height. Inverting gives the level at which a stated uniformity is lost:

$$L = \log_2\!\left(\frac{\pi\,\text{ratio}}{2}\right).$$

A factor of two is exceeded at level 2, a factor of ten at level 4, a factor of a hundred at level 8, and a factor of a thousand at level 11. A geohash of eleven characters — which is an ordinary length for a point identifier — names regions whose areas differ by three orders of magnitude across the Earth.

The expression also settles what the fix has to be, and it is not a smaller cell. Both the numerator and the denominator shrink as the grid refines and the denominator shrinks faster, so no depth escapes: the ratio is monotone in the level with no ceiling anywhere. Fixing it requires changing what the cell boundaries are, which is what a cube or an icosahedron does and what the rest of this ladder measures.

And there is a pleasing consistency with the aspect ratio, which is quoted alongside as the same number. It is the same number for a reason: a polar cell’s east–west extent carries a factor of cos φ that its north–south extent does not, so both the area and the aspect are governed by the same collapse of the parallel’s own length — 78 kilometres tall and half a kilometre wide at level 8, an aspect of 156 against an area ratio of 163, and the small gap between them is the difference between comparing against the equatorial cell and comparing against a square.

Where this stops being the tile pyramid #

This site already has an anchor about square pieces of the world with identifiers: the screen ladder, which is eight essays about the tile pyramid.

The boundary between the two is worth stating precisely because the objects look identical from a distance and are not.

A tile is an image. It exists to be drawn, its size is chosen so that it looks right at a given zoom, and its coordinate system is Web Mercator because that is what browsers render. Everything in that ladder is about appearance: how many tiles cover a screen, what a pixel means on the ground, where a scale bar is right.

A cell is an identifier. It exists to be joined against, it is never necessarily drawn, and its projection is chosen for the arithmetic rather than for the look. Nothing in this ladder draws a map to make its point, which is the separating test.

The two do coincide in one place, and it is instructive: the square costs the poles shows the tile pyramid cutting the world at ±85° so that its tiles stay square, which is a rendering decision with an indexing consequence — the excluded band has no tiles, so it has no addresses either.

The one property every scheme keeps #

Amid all of that variation there is one thing every hierarchical cell scheme does hold exactly, and it is worth naming because it is what makes the identifiers useful at all.

A cell’s children partition it exactly. The four cells at level L+1 whose identifiers extend a cell’s identifier by one step cover precisely that cell and nothing else — not approximately, not up to a tolerance. That is true of the lon/lat scheme, of the cube schemes and of the hexagonal ones, and it is what lets an index be walked: a query can discard a whole subtree by rejecting one identifier.

That property is topological rather than metric. It survives every warp, every choice of solid and every distortion measured in this ladder, because it is a statement about which sets contain which, and containment is what a projection cannot break. Everything else about a cell — its area, its shape, its neighbours’ distances — is metric, and every one of those is fought over for the rest of this ladder.

What an address does not carry #

A cell identifier is a location without a coordinate system attached, and that is a stronger version of the complaint a coordinate without its system is not a location makes about latitude and longitude.

A geohash of gcpvj0 is a region of about 1.2 square kilometres near London, on the WGS84 ellipsoid, with a particular convention about which corner is included. Change the datum and the same string names ground about a hundred metres away — the shift datum shifts dwarf projection errors measures — and nothing in the string says which datum was meant.

That matters more for cells than for coordinates, because an identifier looks self-contained in a way a pair of numbers does not. Two lists of coordinates from different datums can be reprojected into agreement; two lists of cell identifiers from different datums are joined by string equality, and the join succeeds while being wrong.

One number worth carrying away #

If a single figure from this rung is worth remembering it is not any of the areas. It is the ratio: on the obvious scheme, at level 8, the largest cell is 163 times the smallest, and the factor doubles with every further level.

That number is the reason the rest of the ladder exists. A grid whose cells vary by two per cent could be used with a warning in the documentation; a grid whose cells vary by a factor that grows without bound cannot be used for anything that counts, and the schemes people actually run were built by people who had worked that out. What the next two rungs measure is how much better the alternatives are and what they give up to be it — which is the same shape of question which projection is best asks about maps, and gets the same kind of answer.

One consequence of the closed form is worth stating for anybody choosing a level rather than analysing one. Because the ratio depends only on the level and not at all on the region being indexed, a dataset confined to the tropics inherits none of it — the sine’s increments are nearly uniform there, and the worst ratio across ±30° of latitude is 1.15 at every level. The defect belongs to schemes used globally, and a scheme used regionally is as uniform as its region is narrow in latitude.

Where the model stops #

The identifier here is a path down a quadtree, and real schemes add machinery on top: a space-filling curve so that nearby cells have nearby identifiers, a base-32 encoding so the string is short, and a level marker so identifiers of different depths can coexist. None of that changes any area computed above; all of it changes how well the identifiers sort, which is a question about data structures rather than about the sphere.

Cell areas are computed on the sphere. On the ellipsoid every one of them moves by up to a third of a per cent, which is far below the factors of ten this essay is about but is not below the tolerance of somebody using cells to report land areas.

Nothing here says how large a cell should be. That is a question about the data and the query, not about the geometry, and the answer nearly always comes from the smallest feature that must not be merged with its neighbour — which is the same reasoning the tolerance decides the model applies to a survey.

Reading a cell scheme’s numbers off its own construction #

One thing worth extracting before leaving the obvious scheme, because it generalises: the lon/lat grid’s whole behaviour is readable from one line of its own definition.

Its cell boundaries are lines of constant latitude and longitude, so its cell areas are exactly the areas of latitude–longitude cells, which is R²·Δλ·(sin φ₂ − sin φ₁). Everything follows from where the sine appears. The area falls as the cell moves north because a sine’s increments shrink; the aspect blows up because the east–west extent carries a cos φ that the north–south one does not; the spread doubles per level because halving Δφ near the pole nearly quarters the difference of sines while halving it near the equator halves it.

That is the same function, and the same behaviour, that a degree is not a unit of length is about: a degree of longitude is 111 kilometres at the equator and 19 at 80° north. A grid built on degrees inherits that variation exactly, and a grid built on anything else does not have to.

The reason to say it that way is that it predicts the fix. The problem is not the quadtree, the identifier or the hierarchy — all of which the better schemes keep. It is that the boundaries were chosen to be graticule lines, and the graticule is a parameterisation rather than a property of the sphere, which what survives a change of coordinates is the essay about.

Who found it, and when #

Grid identifiers are older than computers: the military grid reference system, which is a lettered lon/lat-like index over UTM zones, dates from the 1940s, and the same idea in a different alphabet goes back to the Ordnance Survey’s letter-pair grid.

The modern schemes are recent and were built by people who needed to index the world for a database rather than to print it. Gustavo Niemeyer published geohash in 2008. Google’s S2 library, built on a tangent-warped cube, was in internal use for years before it was published as open source. Uber’s H3, built on a subdivided icosahedron with hexagonal cells, was published in 2018.

All three replaced a lon/lat grid, and all three did it for the reasons measured above.

Where the ladder goes next #

The obvious repair for a scheme whose cells are the wrong shape is hexagons, which tile the plane with the best perimeter-to-area ratio of any regular polygon and have six equidistant neighbours instead of four adjacent and four diagonal.

They do not tile the sphere. Not badly — at all. Euler’s formula forces exactly twelve pentagons into any such tiling, however many hexagons are used, and the next rung is about what that costs.