The cheapest map that meets its areas

Every density can be met and none is free established two ends of a bracket and could not close it. The upper end is what a construction charges — four exact cartograms of one density, from 57.6° to 104.4° of mean angular deformation. The lower end is a closed form, exact within the radially symmetric class, and the constructions measured against it are not symmetric. The two ends are not comparable, and the shortfall recorded said so.

The bracket closes from an unexpected direction. There is a family of requests whose least cost is exactly zero, the map achieving it can be written down, and the standard construction charges forty-four degrees for one of them.

The condition, which the site already owned #

A conformal map’s areal factor is |f′|², and the logarithm of |f′|² is harmonic wherever f is analytic. That is Liouville’s condition, and a projection written as a condition is the rung where this collection first met it.

Turn it round and it is a statement about cartograms. A cartogram is a map whose areal factor is prescribed, so it can be conformal — costing nothing in angle — exactly when the density it was handed is the areal factor of some conformal map. That is a condition on the density alone:

$$\Delta \log \rho = 0.$$

Nothing about the construction, nothing about the region, nothing about the contrast. A request is free if the Laplacian of its logarithm vanishes.

Exhibiting the free case rather than searching for it #

The natural way to look for a cheap cartogram is to search. The better way is to build the density from the map.

Take $f(z) = e^{\alpha z}/\alpha$ on the equal-area rectangle. Then $|f'(z)|^2 = e^{2\alpha x}$, whose logarithm is $2\alpha x$ and is harmonic by inspection. So the density $\rho \propto e^{2\alpha x}$ is met exactly by f, and f is conformal, so its angular deformation is zero everywhere by construction rather than by measurement.

Measured anyway, on the same machinery every other cartogram here is measured on:

The zero is a real zero: eight decimal places of it, from a differencing of the map rather than from the algebra that built it.

What that does to the earlier rung’s headline #

Every density can be met and none is free measured the cost rising with the contrast, over four constructions and five densities, and the fit is good. The finding survives and its subject has to be named more carefully.

A contrast of 79.8 is at the top of the range the earlier rung measured, and this request costs nothing. Contrast is a property of the density; harmonicity of its logarithm is a different property of the same density; and only the second decides whether the request is free.

That is worth stating as a caution rather than only as a result. Any monotone-looking relationship measured across a family of constructions is a statement about that family, and the phrase “a sharper request costs more” is exactly the kind of sentence that outlives the measurement it came from.

What the bracket looked like before #

It is worth having the earlier rung’s measurement on the page, because the shortfall is about the distance between two numbers and one of them is in it.

A minimum over four constructions says the least cost is at most 57.6°. The radially symmetric closed form says it is at least something, for radially symmetric densities, and none of these four is radially symmetric. Between those two statements there was nothing.

What the free case supplies is a third kind of statement altogether: an exact answer for a family of requests, obtained without searching, and a demonstration that the distance between a construction’s charge and the true floor can be the whole of the charge.

Which parts of the map are paying #

A mean over a window is a summary, and the obstruction it summarises is a field. Reading the two together says where a construction is wasting its money.

The Laplacian of log ρ for two cities peaks on the flanks of the bumps rather than on their summits, in the same places the redistribution’s own angular cost peaks — which is a consistency check rather than a coincidence, since both are second derivatives of the same function. Where the density is flat the obstruction is zero, and there a cartogram is locally a similarity and costs nothing at all.

So the picture of a cartogram’s cost has three layers, and only the first is usually drawn.

The base map’s own deformation, which rung 1 separated out and which is most of a raw figure at high latitudes.

The obstruction, Δ log ρ, which is what the request itself makes unavoidable and which is a property of the data before any map exists.

And the construction’s surplus, which is everything above the obstruction and which the free case shows can be all of it. That third layer is the only one anybody can do anything about, and it is the one no published cartogram reports.

Is it just the edges? #

The obvious objection: the conformal map does not send the rectangle to the rectangle — its image is an annular sector — while the triangular construction is pinned to the rectangle’s edges. Perhaps the forty-four degrees is an edge effect.

It is not an edge effect. What the triangular construction charges is a property of the construction: two nested one-dimensional problems, the second conditioned on the first, which is wildly asymmetric between the two coordinates by design. A cartogram built that way stretches hard in one direction wherever the density has a gradient, and it does that in the middle of the sheet as much as at its edge.

The search over the freedom, and what it recovers #

The other half of the bracket is the upper end, and the shortfall asked for it to be pushed down.

The freedom is exactly the one rung 2 identified: compose any cartogram with any area-preserving map and the result is another cartogram of the same density. So the search is over area-preserving maps, and an area-preserving map of the rectangle to itself is the flow of a divergence-free field — the gradient of a stream function turned through a right angle, with the stream function vanishing on the boundary so nothing leaves.

Between 0.4 and 20 per cent, and the pattern in it is instructive: the search does well on the smooth densities and almost nothing on the sharp ones. A flow with four modes is a very coarse instrument, and the family it is searching is infinite-dimensional. The upper bound is real and it is not tight.

The determinant of the flow stays within 5 × 10⁻⁵ of one over the whole search, which is three orders of magnitude below the quantity being minimised — so the maps the search produces are cartograms rather than near-cartograms.

Where the bracket now stands #

Three statements, and only the first is settled.

On a log-harmonic density the least cost is zero, attained, and the construction’s charge is entirely its own. The bracket is closed and the gap is 43.8 degrees wide.

On every other density the floor is not zero, because a map with that areal factor cannot be conformal anywhere Δ log ρ ≠ 0. What that floor is remains unknown: the search gives 60.3° for two cities and there is no reason to think that is close.

And the floor is not a single number. The obstruction is pointwise — Δ log ρ is a field — so the honest lower bound is a field too, and a mean over a map is a summary of it. That is the same distinction distortion over a region draws between a worst case and an average, arriving here for a quantity nobody has yet computed pointwise.

Why the search does badly where it matters #

The pattern in the search column is worth an explanation rather than an apology, because it says what a better search would have to be.

The search moves the smooth densities by about a fifth and the sharp ones by under two per cent. A stream function with four modes generates a flow whose finest feature is a quarter of the rectangle across; the density of two cities has bumps 8.5 degrees wide. So the flow can rearrange the map on the scale of continents and cannot touch it on the scale of the thing being mapped.

That is not a defect of this particular search. It is the general shape of the problem: the freedom is infinite-dimensional and the cost is concentrated where the density has structure, so any parameterisation coarser than the density itself is spending its degrees of freedom in the wrong places. A search that could reach the floor would need a representation as fine as the request, which is the same size as the map — at which point it is the boundary-value problem again rather than a search over it.

The honest summary of the upper bound is therefore: it is real, it is not tight, and pushing it down further is not a matter of more iterations.

What the free family looks like #

It is worth saying how large the free family is, because log ρ harmonic sounds like a measure-zero coincidence and is not.

The harmonic functions on a rectangle are an infinite-dimensional space: any boundary values at all determine one, so a free density can be built by choosing what the log-density does on the edge and solving. That makes the free requests a set of the same size as the requests themselves, sitting inside them like a hyperplane — dense in one sense and vanishingly thin in another.

The practical consequence is the useful half. Any request is close to a free one, in the sense that the harmonic function agreeing with log ρ on the boundary is available for the asking, and the difference between the two is a function that vanishes on the edge. So a request can be split into a part that costs nothing and a remainder that carries the whole of the cost — which is the decomposition a lower bound would come from, and which this rung does not carry far enough to produce one.

That is the shape of the deferral rather than a restatement of it: what is missing is not a search but a bound on the residual part, and the residual part is now identified.

Where the model stops #

The free family exhibited here is one-parameter. Every log-harmonic density is free, and that is a large family — the harmonic functions on a rectangle are an infinite-dimensional space — but writing down the conformal map for a general one means solving a boundary-value problem, which is the deferral Chebyshev’s criterion has carried from early on and which this rung does not lift.

The search is over four modes of a stream function and one unit of flow time. Doubling the modes was tried and gains under a per cent on the sharp densities, which is evidence that the coarseness is not the whole story and is not evidence about where the floor is.

And the whole of this rung is about angular cost. A cartogram can be judged on distance, on bearing and on betweenness as well, which everything else on the page pays for the areas measures, and a map that is cheapest in angle is not automatically cheapest in any of them.

The generalisation #

The shape of the argument is one this collection keeps arriving at from different directions.

A constrained optimisation has a free case, the free case is a condition on the data rather than on the method, and the condition is usually a partial differential equation nobody looked at. Here the data is a density, the condition is that its logarithm is harmonic, and the equation was already in the library under a different anchor’s name.

The practical version is blunter. Before searching for a cheap map, ask whether the request is free — it is one Laplacian — and if it is, stop searching and write the map down. A construction that charges forty-four degrees for a request that costs nothing is not slightly suboptimal.

What to do when a request is nearly free #

The free case is exhibited rather than searched for, which is the right way to establish that it exists and leaves the practical question open: no real density satisfies the condition exactly, so what is a producer supposed to do with a test that almost always says no?

Read the residual rather than the verdict. The condition is an equation, and an equation applied to a density that does not satisfy it returns a number — how far the requested field is from the free family. That number is computed before any solve, from the request alone, by the same single Laplacian.

And it is a lower bound rather than a diagnosis. A request far from the free family cannot be met cheaply: the distortion any construction must pay is bounded below by how far the request sits from the set of costless ones, and no cleverness in the algorithm closes that gap. A request near the family may still be met expensively by a bad construction — which is exactly the failure the essay reports, forty-four degrees charged for something costing nothing — so the bound convicts the request in one direction and the algorithm in the other.

That is what makes it worth computing first. Two numbers come out of a cartogram: what the construction charged, and what the request cost. If the second is small and the first is large, the construction is at fault and a different one is worth trying. If both are large, no construction will help and the honest response is to say so — the request itself is expensive, and a reader looking at the result is looking at a genuine property of the data rather than an artefact of the method.

Without the bound those two situations are indistinguishable, and the whole cartogram literature is written in the first of them: a construction is proposed, its distortion is reported, and the comparison is against other constructions rather than against what the request was always going to cost.

It also changes what a comparison between two cartogram methods means. Two constructions tested on the same request differ by whatever each wastes above the floor, and the floor is common to both — so a published difference between methods is a difference of waste rather than of quality, and it says nothing about how much of the reported distortion either of them could have avoided. Subtracting the bound first is what turns that comparison into a measurement.

The cost of getting the number is one Laplacian of the requested density, which is less than one iteration of any of the constructions being compared.

Who found it, and when #

Liouville’s theorem on conformal maps dates from 1850 and is the reason three conditions are one too many: a conformal map of the plane is analytic, and its areal factor is therefore not free. The consequence for prescribed-Jacobian problems is standard in the literature on the Monge–Ampère equation, where the same statement appears as the observation that the equation degenerates when the right-hand side is the modulus squared of a derivative.

What is new here is the direction. The cartogram literature reaches for a construction — diffusion, a mesh, an optimal-transport solve — and reports what that construction costs. The question which requests cost nothing is asked of the request rather than of the algorithm, and its answer is available before any algorithm runs.

Where the ladder goes next #

Every density on this ladder has been positive everywhere, because the construction divides by it. The next rung is the density every real cartogram is actually handed, which is zero over most of the sphere.