Five distances of six, and never more

Three rungs of this ladder have leaned on one piece of arithmetic without ever writing it down properly. Four dots on a plane have eight coordinates; sliding the picture costs two and turning it costs one; so five numbers are free and there are six distances. Five against six is why the fourth place is where a flat picture stops being exact, and 2n − 3 against n(n − 1)/2 is why the freedom to do anything about it collapses as the set grows.

Neither statement was established. An optimiser that gets close to five exact distances is not a proof that five is attainable, and a heuristic count of degrees of freedom is not a proof that the sixth is unattainable. This rung does both, and the second half turns out to have a consequence for maps that the first three rungs walked past.

The numerator grows linearly in the number of places and the denominator quadratically, so the fraction has to fall. What is not obvious is that the numerator is exactly 2n − 3 and not something else, and that the bound is tight in both directions.

The upper half: no arrangement holds more #

A distance held exactly is one equation in the coordinates. A picture of n places on a plane has 2n coordinates, and three combinations of them change nothing anybody can see: two translations and one rotation. A reflection changes the picture but is discrete rather than continuous, so it costs no dimension.

That leaves 2n − 3 genuinely free numbers. A system of more than 2n − 3 independent equations in 2n − 3 unknowns has no solution in general, and “in general” is the right qualification: particular sets of distances satisfy more equations than they have freedom for, and those are exactly the sets that lie flat. Every set taken off a sphere is not one of them, which is the rung this ladder starts from.

So the count is an upper bound and it is not tight for every set. It is tight for a set in general position, and a set of places on a sphere is in general position with probability one.

The lower half: a construction, not a fit #

The upper bound would be an accountant’s argument if nothing achieved it. Something does, and it is what a surveyor would do.

Put the first place anywhere. Put the second at its true distance along an axis — that spends the three rigid freedoms, and holds one distance. Then place each remaining point by trilateration: it is at a known distance from the first and a known distance from the second, so it sits where two circles cross, and there are two crossings which are mirror images across the line joining the first two points. Choosing the side the sphere puts it on picks one.

That holds 1 + 2(n − 2) = 2n − 3 distances, exactly, by construction. Nothing is fitted. There is no optimiser, no tolerance and no residual on any held edge.

Five hundred and thirty-seven kilometres is a much larger number than the 0.629 per cent how wrong a flat picture has to be reports as the best available, and the two are not in conflict. The minimax picture spreads the error over all six edges so that no edge carries much; the trilateration concentrates all of it on one. The total is conserved in a rough sense and the distribution is a choice, which is the same trade where a pseudocylindrical puts its error makes for a projection’s own freedom.

The construction also comes with the refusal the argument needs. If the code holding 2n − 3 edges also happened to get a sixth right, the count would mean nothing — so the gate on this file checks that every held edge is exact to better than 10⁻¹² and that no unheld edge is right to better than 10⁻⁶. On sixteen cities the closest unheld edge is out by 0.093 per cent, which is a thousand times outside the tolerance, so nothing came right by accident.

The side the sphere puts it on #

One step of the construction is a choice and it is worth being explicit about it, because a construction with an arbitrary choice in it is not a construction.

Two circles cross in two places, and the two are mirror images across the line joining the base points. Both hold the same 2n − 3 distances exactly, so the count is indifferent between them — and the two pictures are genuinely different, because the unheld distances come out differently.

The side is taken from the sphere: for each place, the sign of the triple product of the two base points’ position vectors with its own, which says which side of the great circle through the base points it actually lies on. That is a fact about the configuration and not about any radius, which is what lets the same construction run on a page of any curvature in the rung that follows without changing the answer for a reason that has nothing to do with curvature.

Reflecting one place is what turns a picture of the world into a picture of its mirror image in one city, and it is worth knowing that the count does not notice.

Which 2n − 3 is not a free choice #

There is a second half to the count that the arithmetic above hides, and it matters for what follows.

Trilateration holds a particular set of edges: everything touching the first two places. That is one choice of 2n − 3, and not every choice of 2n − 3 works. Take sixteen places and pick twenty-nine distances all among the first six of them — there are only fifteen distances among six places, so the choice is impossible; pick twenty-nine that leave the sixteenth place touched by only one, and that place can swing on its single edge while the count says the picture is rigid.

The condition a workable choice satisfies is Laman’s, from 1970: a set of 2n − 3 edges makes a plane picture rigid exactly when every subset of k places carries at most 2k − 3 of them. It is a counting condition applied to every subset rather than to the whole, and it is the reason “which distances” is a combinatorial question with a real answer rather than a matter of preference.

For this ladder the consequence is one sentence. A map maker who wants a particular set of distances to be exact cannot simply choose 2n − 3 of them; the choice has to be rigid, and a rigid choice constrains which places may be the well-connected ones.

What a centred map spends, and what it leaves #

Now the consequence for maps, which the three rungs below this one all walked past.

An azimuthal equidistant map centred on a place is exactly right about every distance from that place. That is n − 1 exact distances. The plane allows 2n − 3. The difference is n − 2, and it is the number of further distances a flat picture could hold that this projection does not.

Fourteen distances unspent. That is not a criticism of the projection so much as a description of what a projection is: a rule fixed before the set of places is known cannot spend its freedom on the particular places that turn up.

The point sharpens when the two are put side by side in the same units.

Why the unspent freedom is not recoverable #

A reader who has followed the count this far will ask the obvious question: could a projection be built that spends all 2n − 3?

It could, for one set of places, and it would not be a projection. Trilateration from the first two places is exactly such a construction, and it holds twenty-nine distances on sixteen cities — but the rule it follows depends on which sixteen, so a seventeenth city arriving changes nothing about the twenty-nine already held and cannot itself be placed by the same recipe without picking new base points.

That is the trade this ladder has been circling from three directions. The best flat picture is not a map lists what a free arrangement gives up — an inverse, everything outside the set, stability, properties — and the count here says what it buys: 2n − 3 exact distances instead of n − 1. Whether that is a good exchange depends entirely on whether anybody will ever ask about a place outside the set, which for a map is always and for a distance table is never.

There is a third position between the two and the subject has used it for centuries without describing it this way. A survey network holds a set of measured distances exactly at a set of control points and interpolates everything else; where the control points are shows what that does to what can be recovered, and the network’s answer is decided before it is measured prices how much of that answer the geometry fixed in advance. A network is a picture that spends its freedom on the places it has measured, and a projection is what fills in between them.

The same count, in a surveyor’s units #

The construction above is trilateration and the word is not borrowed. It is what a survey does when it measures distances rather than angles, and the count has been the working arithmetic of the field for as long as there have been networks.

A survey network of n stations in the plane has 2n − 3 degrees of freedom once its position, orientation and — for a trilateration — nothing else are fixed. Measuring exactly 2n − 3 distances determines it and leaves nothing over; measuring more produces a system with no exact solution, and the excess is called redundancy. A traverse must close is the smallest instance: a closed figure is a network with one more observation than it needs, and the misclosure is what the extra observation says about the others.

So the whole apparatus of least squares in surveying exists because real networks are measured with more than 2n − 3 observations on purpose, and the residuals are the information the redundancy buys. The weights are a guess the solve believes is about what happens to those residuals when the observations are not equally trusted.

What is different here is the sign of the problem. A survey has surplus observations of a configuration that exists, and the surplus is a check. This ladder has surplus constraints on a configuration that does not exist, and the surplus is the impossibility. The arithmetic is identical and the two situations are opposite, which is why the same count reads as a virtue in one field and as a theorem in the other.

Why the count is not 2n − 4, or 2n − 2 #

Two off-by-one errors are available here and both have been made in print by somebody, so they are worth blocking.

A reflection is not a degree of freedom. Flipping the picture over produces a different arrangement with the same distances, so the map from arrangements to distance sets is two-to-one rather than one-to-one — but a reflection is an isolated operation rather than a continuous family, so it removes no dimension and the count stays 2n − 3. What it does mean is that the construction has a choice to make, which the previous section is about.

And a scale is not a degree of freedom here, though it is one everywhere else in this ladder. Every other rung scores a picture after allowing it a free multiplier, because a drawing has no natural size and only proportions are meaningful. This rung holds distances in kilometres, so the scale is fixed at one by fiat and the count is 2n − 3. Allow the scale to float and a picture can hold 2n − 2 ratios of distances while holding 2n − 3 distances only up to a common factor — the same statement in different units, and the reason the two counts differ by exactly one.

Neither correction changes anything above, because 2n − 3 and 2n − 2 are the same to the precision the asymptote is quoted at. They are worth separating because a reader checking the arithmetic against a picture will find the discrepancy and should know which convention produced it.

The number a hundred places gets #

The rule of thumb worth carrying out of this rung is the asymptote.

The share is (4n − 6)/(n² − n), which is 4/n to within a few per cent for any n above about ten. So a picture of a hundred places gets four per cent of its distances exactly right and ninety-six per cent of them wrong; a picture of a thousand gets four in a thousand. As a set grows, a flat picture of it approaches being wrong about everything, and the approach is fast.

That is the counting explanation for a result the previous rung measured and could not account for. On four world cities the best free arrangement beats the best projection by a factor of 13.17; on sixteen, by 1.08. The freedom available per constraint falls from 83 per cent to 24 across that range, and by sixteen places nearly everything about the picture is forced by the distances themselves. There is very little left for an optimiser to do that a projection has not already done, and the eight per cent it manages is what remains of a factor of thirteen.

It also explains why the azimuthal equidistant keeps winning. Its n − 1 exact distances are a fraction 2/n of the total, against the 4/n a free picture could reach — so the map holds half of what the plane allows, at every size, and the half it holds is the half a reader of a centred map is most likely to want.

Nothing here needed a sphere #

It is worth noticing how little of this rung is about the Earth.

The count is a statement about the plane: 2n coordinates, three rigid motions, one equation per held distance. Laman’s condition is a statement about graphs. The trilateration is a ruler-and-compass construction. None of the three mentions curvature, and every one of them would hold for a set of distances invented at random.

What the sphere supplies is only that the leftover constraints are violated — that the 6 − 5 = 1 unheld distance on four cities comes out 6.87 per cent wrong rather than right. A set of distances taken from a flat map would run through the identical construction and every unheld edge would come out exact, which is the refusal four cities that cannot be drawn to scale makes with chordal distances and the same machinery makes here.

That separation is what makes the rung portable. The count says how much can be right; the surface says how wrong the rest is; and the two multiply rather than interact.

Where the exact distances should be put #

The count says how many and Laman says which combinations are legal. Neither says which legal combination is best, and that question has an answer worth stating because it is the only design decision this rung leaves open.

The trilateration above holds every edge touching the first two places, which puts fourteen of the twenty-nine exact distances on one place and fourteen on another. That is a picture with two hubs. The azimuthal equidistant puts all fifteen of its exact distances on one, which is a picture with one hub and is not rigid on its own — a star of n − 1 edges is n − 2 short of 2n − 3, so the map is holding a set of distances that would leave the picture free to flex, and it is the projection rather than the distances that stops it flexing.

Spread instead: hold a chain of consecutive distances round a ring of places plus enough diagonals to satisfy Laman, and the exact distances are the ones between neighbours. That is the arrangement a reader of a regional map wants, because the pairs anybody measures on a map are the near ones.

So the three sensible policies are the hub, the pair of hubs and the ring, and they correspond to three real objects: a distance-from-here map, a trilateration network, and something no projection in this collection’s library is. The third is worth naming because it is what a road atlas’s mileage chart implicitly is, and because it is the one case where the exact distances would be the ones a reader actually uses.

The escape nobody has priced #

Everything in this ladder has taken the sheet of paper as given. Four rungs have measured what a flat picture cannot do, how badly, against what alternative, and with how much freedom — and every one of them has treated flatness as the constraint and looked for the best behaviour inside it.

That leaves the constraint itself unexamined, and there are exactly three ways to relax it: give the picture more dimensions, give it curvature, or give up that the reader measures it with a ruler. Two of those have obvious answers that turn out to be wrong. The first is the one everybody expects to work — four points that will not lie in a plane lie in a space, surely — and on distances taken off a sphere it buys nothing whatever, to fifteen decimal places.