A map that meets its target can fold

A cartogram is a deformation — built to a density it was handed, and one of infinitely many that meet it — and a deformation can go too far. Somewhere past the point where a region is merely stretched, it turns inside out: the map sends two patches of ground to the same patch of page with opposite orientations, and what is drawn is not a map of anything.

The interesting part is not that this happens. It is where the boundary between the two behaviours sits, and the answer is that it depends on things the specification says nothing about — the path taken to the answer and the size of the steps taken along it — while the answer itself is perfectly safe.

The exact construction cannot fold, and that is a theorem #

Start with the good news, because it is exact and it is short.

The triangular construction has a lower-triangular Jacobian: the first coordinate of the answer depends only on the first coordinate of the argument, so the off-diagonal entry above the diagonal is identically zero. The determinant of a triangular matrix is the product of its diagonal, and both diagonal entries are strictly positive — one is $2\pi$ times a marginal density and the other is $2$ times a conditional density, and the stated densities are bounded away from zero.

So the determinant is positive everywhere, and the map is orientation-preserving everywhere, and there is nothing to check. Not a tolerance, not a sampled minimum, not a claim about the cases tried: a structural fact about the construction.

Measured anyway — because a structural fact that the arithmetic contradicts is a bug — the smallest determinant over four hundred samples of the sharpest stated density is 0.375, which is positive by a comfortable margin and is the density’s own floor divided by its mean.

The path from the undeformed map cannot fold either #

The plan for this rung predicted the opposite, and the arithmetic corrected it before any figure was drawn.

The obvious thing that folds is a morph: take the identity and the finished cartogram and interpolate between them, $T_s = (1-s)\,\mathrm{Id} + s\,T$, which is what every animation of a cartogram computes. Both ends are diffeomorphisms; nothing says the path between them is.

Along that path the Jacobian is $(1-s)I + s\,\mathrm{D}T$, and its determinant is a quadratic in $s$:

$$\det = (1-s)^2 + s(1-s)\,\mathrm{tr}\,\mathrm{D}T + s^2\det\mathrm{D}T.$$

For a lower-triangular $\mathrm{D}T$ with diagonal $p, q$ the off-diagonal term never enters — a triangular matrix’s determinant does not see it — so this is the same quadratic as for the diagonal matrix, and its roots are $1/(1-p)$ and $1/(1-q)$. Those lie in $(0, 1)$ only when $p$ or $q$ is negative, which for a positive density they never are.

So the path from the undeformed map to a triangular cartogram provably cannot fold, at any density, at any contrast. Measured over four hundred samples: nought.

The path between two answers does fold #

What does fold is the path between two different cartograms of the same data — and since the previous rung established that there are infinitely many, that path is not exotic. It is the path an animation takes between two editions of a map, or between two algorithms’ output, or between two frames of an interactive control.

The determinant along $(1-s)J_1 + s J_2$ is again a quadratic in $s$, now with three independent coefficients, and its roots are available in closed form from the determinants at $s = 0$, $s = \tfrac12$ and $s = 1$. So the fold is not a numerical accident to be discovered by refining a sweep. It is an exactly locatable property of the pair of maps, computed once per point, and the earliest fold anywhere on this pair is at 1.6 per cent of the way across.

That number is the alarming one. A viewer dragging a slider between two correct maps of the same data spends the first two per cent of the drag looking at a correct map and the remaining ninety-eight looking at one with thirty-eight inverted cells.

Why the mid-point of two good maps is not good #

The reason is worth stating in words, because the algebra hides it.

Averaging two maps averages their Jacobians, and the determinant is not a linear function of the matrix — which is also why an average of ellipses is not an ellipse. Two matrices with determinant one average to a matrix whose determinant can be anything from one down to negative values — take $\mathrm{diag}(k, 1/k)$ and its transpose-inverse and average them, and the determinant falls as $k$ grows.

So the operation that looks safest — blend two things that are both right — is precisely the one the quantity being preserved is not preserved under. The average of two projections made this argument about conformality; here the same non-linearity appears with orientation itself at stake, which is a worse failure than a lost property.

What a fold does to everything downstream #

A fold is not merely an ugly picture. It breaks three things a map is used for, and it breaks them silently.

Inversion stops working. A folded map sends two ground points to one page point, so there is no inverse there — the same failure a map that cannot be read backwards is about, arriving in a construction rather than in a formula. Any query that starts from a page position and asks what is underneath has two answers and no way to choose.

The indicatrix stops existing. At the moment of folding the determinant passes through zero, so one principal scale factor is zero and the ellipse has collapsed to a segment. That is the degenerate case the indicatrix at a point that has none already catalogued for the poles of cylindrical projections, arriving here at an interior point of an otherwise ordinary map.

Areas start double-counting, and computing an area needs a surface that the fold has locally destroyed. The areas the construction was built to get right are computed as integrals of a determinant, and past the fold the determinant has the wrong sign. Integrated without an absolute value the folded region subtracts; integrated with one it adds twice. Either way the quantity the whole map exists to convey is wrong exactly where the map is worst, and no check on the unfolded cells detects it.

The construction that folds in practice #

The blend is a way of getting a fold on purpose. The way one arrives by accident is an iterative construction, and the crude ancestor of every published cartogram algorithm is a mesh pulled towards its targets in steps.

Each cell asks for its linear size to change by the square root of its density ratio, and each vertex moves by the sum of the pulls of the cells around it, scaled by a step. Nothing in that scheme knows where its neighbours are. A vertex pulled hard enough goes past one, the quad it belongs to acquires a negative signed area, and the picture acquires a crease that no later iteration removes.

The threshold, and what it is a threshold in #

The threshold is not a property of the step alone or of the contrast alone. What a cell asks for is the square root of its density ratio, so the displacement per step scales as $\sqrt{C} - 1$, and the step that survives falls with it. A construction validated at a contrast of two and shipped at a contrast of thirty-two is taking steps eight times too large and has no way to notice.

The failure mode is the worst available. A fold does not raise an exception, does not fail a convergence test and does not make the areas wrong in any obvious way — the areas of the unfolded cells are still approximately right. What it produces is a picture with a crease in it, which a reader interprets as a feature of the data.

The threshold table is a law rather than nine measurements, and it is worth checking as one. If the displacement a cell asks for per step scales as √C − 1, then the largest safe step scales as its reciprocal, and the product of the two should be constant. Taking the ends of the sweep: at a contrast of two the step is 0.4 and √C − 1 is 0.414, giving 0.166; at thirty-two the step is 0.05 and √C − 1 is 4.657, giving 0.233.

Those agree to forty per cent over a sixteenfold range of contrast, which is the law working and is not the law being exact. What is left over is the geometry: the displacement a vertex makes is the sum of the pulls of the cells around it, so a vertex on the flank of a sharp bump has neighbours asking for different things and partially cancelling, while one in a gentle field has neighbours that agree. The cancellation is worth more at high contrast, which is the direction the residual moves.

The useful form of the law is the reciprocal. A construction validated at contrast C₁ and shipped at C₂ is taking steps too large by a factor of about (√C₂ − 1)/(√C₁ − 1), and that factor is available before anything is run — the contrast of a density is one division on the data. A step limiter keyed to it would remove the whole failure at the cost of one line, and the reason none is present in the crude construction is that nothing in the scheme’s own output announces that it is needed.

The exact one is not the one anybody uses #

Here is the pairing the whole ladder turns on, stated as two facts that are individually unremarkable and jointly awkward.

The construction that meets its target exactly is the triangular one, and nobody uses it, because it produces a picture that is a smear. The construction everybody uses is the diffusion one, and it does not meet its target: it has to be truncated in time, discretised in space and integrated in steps, and each of the three leaves a residual.

And the residual is not a fixed property of the implementation. It rises with the contrast of the data — from 1.3 per cent on a gentle density to 21.4 per cent on a sharp one — so the cartograms that most need to be right about their areas are the ones most likely to be wrong about them. A cartogram is drawn precisely because the contrast is dramatic, which is to say precisely where the method’s error is largest.

Where the residual comes from #

Three sources, and they behave differently.

Time truncation. The flow runs to infinite time and stops at a finite one. The modes of the heat equation on the rectangle decay as $e^{-\lambda t}$ with $\lambda \geq 1$, so stopping at $t = 9$ leaves about $10^{-4}$ of the density variation unspread. That is negligible and is not the problem.

Spatial resolution. The velocity field is sampled on a grid and interpolated between its nodes. Refining the grid from 96 × 48 to 192 × 96 halves the residual over the middle of the map and leaves the polar strip alone — because in the equal-area rectangle the poles sit at the edges, where the last cell of any grid covers everything above about 78° whatever its resolution.

Integration. The positions are stepped forward with a finite scheme. This is the source that folds, and it is also the one an implementer controls most directly and understands least.

The honest summary is that over the middle sixty degrees of latitude the diffusion construction is good to about one part in a hundred on a gentle density and one in five on a sharp one, and that this is a statement about the method rather than about any particular program.

Two guarantees that do not compose #

There is a general shape here worth carrying out of this essay, because the fleet meets it repeatedly.

Two objects each carry a guarantee. The exact triangular map is orientation-preserving by the structure of its Jacobian. The exact diffusion flow is orientation-preserving because it is the flow of a smooth vector field for a finite time. Both guarantees are airtight and neither survives the operations actually performed on them: interpolating between two guaranteed maps, or stepping along a guaranteed flow with a finite step.

The reason is the same in both cases. The guarantee is a property of a point in a space of maps, and the operations move through that space along paths the guarantee says nothing about. A straight line between two points of a set need not stay in the set unless the set is convex, and the set of orientation-preserving maps is not convex.

That is why the fold is locatable rather than mysterious. Once the question is put as “where does this path leave the set”, the answer is a root of the determinant along the path, and along a straight-line path the determinant of a two-by-two matrix is a quadratic. There is nothing to search.

Where the model stops #

The mesh construction here is deliberately crude — it is the ancestor rather than a current implementation, and a modern one carries a line search, a step limiter and often an explicit fold check. Those measures work, and the reason they exist is that the failure is real.

What none of them removes is the underlying fact: the smooth object has a guarantee and the computed object does not inherit it. A theorem about a continuum flow is not a theorem about any program that approximates it, and the gap between the two is a step size.

What the site’s own gate had to be told #

The assertion this rung ships is in two halves, and getting the halves right took a correction.

The first version asserted that the path from the undeformed map folds, because the plan said it would. It does not, and the arithmetic said so on the first run: nought of four hundred and eight samples, at every density tried. Weakening the assertion to accommodate that would have been the wrong repair — an assertion that has never rejected anything proves nothing, and one weakened until it passes proves less.

The repair was to find what the claim should have been. The path from the identity cannot fold, provably, for a lower-triangular Jacobian; the path between two different cartograms of the same data can and does. So the assertion now requires both: zero folds on the first path and a positive count on the second. It fails if either half moves, which means it fails if the triangular construction stops being triangular and it fails if the two orders stop being different maps.

That is a better check than the one intended, and it exists because the first one was wrong in a way the numbers could see.

Who found it, and when #

The site’s own mixing of two projections can fold too, which is the same arithmetic in a different family. Gastner and Newman’s diffusion method is from 2004 and its selling point was exactly the guarantee: the flow is a diffeomorphism, so the map cannot tear, cannot fold, and preserves the topology of whatever is drawn on it. That is true of the flow.

The folding of discretised versions is folklore rather than literature — it appears in bug reports, in step-limiting code, and in the tuning parameters of published implementations, which is where a well-known failure lives when nobody has written it down. What is measurable here is the threshold, and the fact that it moves with the data rather than staying where an implementer put it.

Where the ladder goes next #

Everything so far has been about the areas and about what happens near them. The last rung asks the question a reader asks: given a map whose areas are exactly right, what is left — what happens to a distance, a bearing, a shape, and the order of places along a line.