A label belongs to no tile

Nine rungs of this ladder price the tile as a piece of geometry: its ground size, its place in a pyramid, its integer lattice, its seam, the numbers its renderer runs out of.

Everything they measure is local. A tile’s geometry is decided by the tile’s own contents, so a tile can be rendered alone, in any order, by a machine that has never seen its neighbours — which is the whole reason the pyramid works.

A label is not local.

Why a label is a different kind of object #

A road is drawn where the road is. A boundary is drawn where the boundary is. Clip either at a tile edge, draw the pieces separately, and the result is the same picture — which is what a tile is drawn without its neighbours establishes for geometry and where its exceptions are.

A label is drawn where nothing else already is. Its position is decided by an anchor and its survival by a collision test against every other label that has already been placed, in order of priority. That is a global relation: whether a name appears depends on what is beside it, and what is beside it may be in another tile.

So a tiled renderer is running a global algorithm on local information, and the question is not whether that produces the right answer — it cannot — but how far wrong it goes.

What was computed, and how #

Everything here is in page pixels, because a label is a page object and its size is in pixels by definition. No projection enters, which is deliberate: this is a failure of tiling rather than of mapping, and mixing the two would make it impossible to attribute.

The field is 260 stated label boxes on a 1,024-pixel page: anchors from a stated hash, widths between 50 and 118 pixels, a stated priority order. The placement rule is the one every renderer uses — take the labels in priority order and keep each one whose box overlaps nothing already kept.

Globally, that keeps 156 of the 260.

Per tile, each 256-pixel tile takes the labels whose anchors fall inside it, runs the same rule on that set alone, and paints what it owns. That keeps 170.

The dominant failure is a label that should not be there. Fifteen names survive because the thing that would have suppressed them was in the next tile, and one name goes missing. That asymmetry is not an accident of this field: the tiled rule sees fewer competitors, so it keeps more.

It is also exactly what a reader sees on a real web map — two names overlapping across a tile boundary, in a rendering that suppresses overlaps everywhere else.

The control #

The check that makes the measurement mean anything: run it with one tile covering the whole page. The two rules are then the same rule on the same set, and the disagreement is zero — no missing labels, no extras, no doubles.

That is the assertion this rung ships, and it rejects the obvious way to get a spurious result. A difference between two placements could easily be an ordering bug, a tie broken differently, or an off-by-one in the overlap test, and every one of those would show up in the single-tile case as well.

How the disagreement scales #

The bound is a perimeter fraction and it grows as the tiles shrink, which is why halving the tile size roughly doubles the damage. The measured figure stays well under it, because being at risk is necessary and not sufficient: a label near a boundary with no neighbour on the other side is placed identically either way.

Two consequences follow immediately. A finer tiling is worse, so the pressure towards small tiles for bandwidth — which a screen map is a pyramid of tiles prices in every other respect — runs against correct labelling. And a larger label is worse in the same proportion, so a design decision about type size is also a decision about how many names are misplaced.

The repair, and what it costs #

Every real vector-tile scheme carries a buffer: each tile is given some margin of its neighbours’ content, as context to clip against and to place against.

The buffer works, and it works for a reason that says how large it has to be. A collision is a chain: this label blocks that one, which would have blocked a third. A buffer truncates the chain at whatever distance it reaches, so the buffer needed is the length of the longest chain that matters — and chains get longer as the field gets denser.

At the density a city centre reaches, the context a tile needs is the tile itself. Every label in the buffer is loaded, decoded, laid out and thrown away by every tile that can see it, so a buffer of a whole tile means every label is processed nine times, and the independence tiling exists for has been bought back at the price it was sold for.

The buffer is a page distance and the tile is a page distance #

The buffer table is quoted in pixels against a 256-pixel tile, and converting it into work says something the pixel figures hide.

A tile of side T given a buffer b must load and lay out everything within (T + 2b)² of page area to paint T² of it, so the redundancy factor is (1 + 2b/T)². For the five densities measured that is:

At the city-centre density every label is laid out nine times and eight of those results are thrown away. That is the number the bandwidth argument for tiles was supposed to be avoiding.

And the factor gets worse as tiles get smaller, quadratically. The buffer needed is set by the length of a collision chain, which is a distance in page pixels — a function of how big type is and how close names are, and not a function of how the page happens to be cut. So b is fixed while T varies, and (1 + 2b/T)² is a factor of 1.9 on 512-pixel tiles, 3.1 on 256, 6.3 on 128 and 16 on 64.

That closes the argument the earlier section opens. Halving the tile size doubles the number of misplaced labels and nearly doubles the cost of the buffer that would fix them, because the fix is measured in the units of the problem rather than the units of the partition. There is no tile size at which labelling is cheap: large tiles are cheap and defeat the reason for tiling, and small tiles are the case where the repair costs most.

It also explains why the buffer is not simply set to whatever is needed. A specification that says use a 64-pixel buffer is choosing a fixed cost of 1.6 times on 256-pixel tiles, which is affordable, and accepting the misplacements that longer chains produce. The measurement above says which densities that choice is wrong for, and they are the densities on which a reader spends most of their time.

What schemes actually do instead #

The measurement above prices the honest fix. Real schemes take cheaper ones, and each has a visible signature.

Assign every label to exactly one tile by its anchor, and let the client resolve collisions after assembling the tiles it holds. This is what a modern vector-tile client does, and it moves the problem rather than solving it: the client now has a global view of the tiles it has loaded, so a label’s fate changes as tiles arrive and as the user pans. A name can appear, disappear and reappear without the data changing, which is the flicker every such map has.

Pre-compute the placement server-side at every zoom. Exact, and it gives up the client’s freedom to rotate the map or change the type size, because a placement is only valid for the page it was computed on.

Give labels a global priority and let overlaps happen. Cheapest, and it is what the fifteen extra labels in the table above are.

None of the three is wrong. What none of them is, is the local operation the rest of the pyramid consists of, and pretending otherwise is where the flicker comes from.

There is a second reading of the same factor, and it is about which quantity a scheme is optimising. Tiles are cut small so that a client fetches only what it needs; buffers are added so that a tile can be rendered correctly. The first argues for a small T and the second for a small b/T, and the two cannot both be had because b is set by the content rather than by the cut. A scheme therefore chooses which of the two it is willing to be wrong about, and every scheme in use chooses the same way — a modest fixed buffer, correct labelling abandoned, and the client asked to make up the difference.

What a reader actually notices #

The counts above are a fair measure of the algorithm and an unfair measure of the experience, and the difference is worth stating because it changes which of the failures matters.

A missing label is nearly invisible. A reader who does not know a name is there has no way to notice it is not. One label went missing in the whole field, and it would have gone unremarked at ten.

An extra label is very visible, because it appears as two names overlapping — the one thing the placement rule exists to prevent, occurring in a rendering that has suppressed hundreds of others successfully. Fifteen of them, all concentrated on tile boundaries, which is a pattern a reader learns to see.

A doubled label is visible and looks like a bug, and it is the one failure a buffer removes completely, because a scheme that lets a tile paint only what it owns cannot draw the same anchor twice.

So the three failures rank in the reverse order of their counts. The rarest is the most conspicuous and the commonest is the least, which is why the practical priority in every renderer is to stop overlaps at boundaries rather than to reproduce the global placement — a different objective, met by different means, and one this measurement does not score. It is also the objective a buffer meets soonest: the doubled labels vanish at any buffer at all, the boundary overlaps at a modest one, and only the exact reproduction of the global placement needs the large one.

Where the model stops #

A label has one anchor here. Real labelling moves a label around its feature — eight candidate positions for a point, an arbitrary offset along a line — and that freedom reduces the collision rate at every tile size. It does not change the argument: whether a candidate position is free is still a question about the neighbours.

Priority is stated rather than derived. A renderer ranks labels by the feature’s own importance, and a stable global ranking is what makes the greedy rule deterministic. Nothing here depends on the ranking being anything in particular, only on its being the same for both placements.

And the page is flat. No projection appears anywhere above, which is the point: this is a tiling failure and would happen identically on a plane. The projection’s own contribution — that a tile covers a different amount of ground at every latitude, so label density in page terms is not label density on the ground — is the road is drawn two pixels wide and multiplies everything here by a factor that varies over the sheet.

It is worth noting what the measurement deliberately does not include. Nothing here models the client’s own collision pass, the one a modern vector-tile renderer runs over the tiles it holds. That pass genuinely fixes the boundary overlaps for the tiles in memory, and it introduces the failure in exchange: the set of tiles in memory changes as the reader pans, so the same label’s fate changes with it. Trading a static error for a dynamic one is a reasonable trade and it is not the same thing as removing the error.

The generalisation #

A pyramid of tiles is a partition of the page, and it is only a valid decomposition for operations that are local.

Drawing a road is local. Clipping a polygon is local, and a vector tile has an integer grid prices the quantisation that makes it nearly so. Choosing which names to show is not, and neither is anything else that depends on what is nearby: symbol displacement, line generalisation with a neighbour constraint, a shared boundary two features hold.

The collection has the same structure at a different scale. A national grid is a partition into zones, and everything computed inside a zone is right while anything computed across a boundary needs both. A polyhedral map is a partition into faces, and a feature crossing a seam is the same argument with a projection instead of a renderer.

The shared shape is that the decomposition is chosen for one property and then relied on for others. Tiles were chosen so that a client could fetch what it needs; the assumption that a tile can be rendered alone came free with it and is true of most of what a renderer does. The label is the exception, and it is the part of the map a reader actually reads.

Why the pyramid does not rescue it #

One more repair suggests itself and does not work, and it is worth ruling out because it is the natural move on a pyramid.

Place the labels once at the coarsest zoom and inherit the placement downwards. Then every tile at every level is consistent with its parent, and the collision resolution has been done once, globally, on a small page.

It fails because a label’s page size is fixed in pixels and its ground footprint therefore halves at every zoom step — which is the whole content of zoom is a ladder. A label that collides at zoom 8 has room at zoom 12, so a placement inherited downwards suppresses names that should appear, and the map gets emptier as the reader zooms in, which is the opposite of what a pyramid is for.

The placement is therefore genuinely per zoom level, and there are around twenty of them. That is not a difficulty by itself — the work is small — but it removes the last version of the argument in which the collision problem is solved once.

Who found it, and when #

Automated label placement has been studied since the 1970s and is known to be NP-hard in its general form; the greedy priority rule used here is the standard practical approximation and is what every mapping library ships. Buffers are in every vector-tile specification, and the recommended sizes are exactly the fractions of a tile measured above.

What appears not to be written down is the shape of the trade — that the buffer needed grows with density until it is the tile itself, so there is no buffer size that is both small and sufficient. The engineering answer, moving collision resolution to the client, is well known as a technique and is rarely described as what it is: an admission that the operation is not tileable.

Where the ladder goes next #

Ten rungs price a screen map’s geometry, its numbers, its tiles and now the one thing on it that is not geometry. What none of them prices is time — a web map is not a picture but a sequence of them, tiles arrive in an order nobody controls, and every quantity measured here is a function of which ones have arrived. The map a reader sees for the first second is a different map, and it is the one most readers see.