Where the shortest route stops being the only one

Rung four of this ladder found the one place on a sphere where the question what is the shortest route has no single answer. From any point, every great circle reaches the antipode, all of them are the same length, and there is no reason to prefer one. It is one point, and the essay treated it as a curiosity of the sphere.

The Earth is not a sphere. Geodesics on an ellipsoid are harder, do not close after one circuit, and do not all reach the same place — and the set of points with more than one shortest route stops being a point.

The symmetry that makes it computable #

The set of points where a geodesic stops being the shortest route is the cut locus, and finding one in general is hard: it requires knowing, for every point, whether some other geodesic arrives sooner.

For a body of revolution one case is tractable and it is the case that matters. Fire a geodesic from P at azimuth α, and fire another at −α. The surface is symmetric under reflection in P’s own meridian, so the second geodesic is the mirror image of the first — same length at every stage, same behaviour, arriving wherever the first arrives, reflected. The two therefore have equal length wherever they meet, and by symmetry they meet on the antipodal meridian.

Each azimuth α thus produces a point with two shortest routes, and the whole set of them is the cut locus. On a sphere every one of those meetings is the antipode; on an oblate ellipsoid the meeting latitude is a function of α.

Vincenty’s algorithm is deliberately not used anywhere in this essay. It returns the shortest distance between two points, and the question here is where there stop being one of those. Every path is integrated from the geodesic equations instead — the same integration that separates a geodesic from a normal section, and the meeting point is found by bisection on the arc length until the longitude crosses 180°.

Sixty-six kilometres of antipode #

The answer at the equator is the largest, and it is a real distance.

The direction of that trend is the opposite of the obvious guess, and it has a one-line reason. Every geodesic from a pole is a meridian, and every meridian meets every other at the other pole. So a polar point’s cut locus is a single point on any body of revolution, sphere or not, and the ellipsoid’s departure from a sphere shows itself furthest from the axis rather than nearest to it.

The distances involved vary too. For a point at 15° north the two-route points are reached after between 20,035 and 20,066 kilometres — a spread of 31 km along a 60-km arc. So not only is “the antipode” a stretch of ground rather than a place; the distance to it is not one number either.

The shape of the arc #

The cut locus is a segment of the antipodal meridian, and its two ends are worth naming because they are the two extreme azimuths.

A geodesic leaving due east or due west — azimuth 90° — is the one that stays lowest, and its mirror is itself. For a point at 15° north those two arrive at 15.009° south: essentially the geometric antipode, and reached after 20,035 km, the shortest of the family.

A geodesic leaving nearly due north or due south — azimuth approaching 0° — travels over the pole, and its mirror is the path over the pole on the other side. For the same point those two meet at 15.563° south, after 20,066 km. That is the far end of the arc, and it is the longest member of the family.

So the arc runs from the geometric antipode away from the equator, and the routes that reach its far end are the polar ones. That ordering is a direct consequence of the ellipsoid being oblate: a polar route crosses the flattened part of the body, where a degree of latitude is longest, and it accumulates its extra distance there.

The whole spread is half a degree of latitude and thirty-one kilometres of distance, on a journey of twenty thousand.

What that means for a route #

The practical consequence is smaller than the geometry suggests, and saying so is more useful than overstating it.

Nobody flies to their antipode. The commercial routes that come closest — a great many pairs of cities are within a few degrees of antipodal — are long enough that the choice between two nearly equal routes is dominated by winds, airspace and diversion airports, which are questions this collection does not answer and which the rung about the quickest route has already separated from the shortest one.

What the cut locus does affect is software, and it affects it in a way that shows up as flakiness rather than as error. An inverse geodesic solver near the cut locus is solving a problem with two nearly equal solutions, so it is ill-conditioned: small changes in the endpoints swing the answer’s azimuth by large amounts, and different implementations return different azimuths for the same pair. Vincenty’s iteration is famously non-convergent for nearly antipodal points, which is a symptom of exactly this and is why Karney’s 2013 algorithm exists.

The rule for anyone using such a solver is short: the distance near the cut locus is well determined and the azimuth is not. Code that uses the returned azimuth for anything — drawing the route, computing a bearing, flying it in straight legs — is using the least reliable output of the calculation.

Why the sphere hides it #

It is worth being explicit about what makes the sphere the exception rather than the rule, because the sphere’s behaviour is so tidy that it reads as the natural case.

On a sphere every geodesic is a great circle, every great circle through P also passes through P’s antipode, and every one of them takes exactly half a circumference to get there. Three separate coincidences, and all three are consequences of the same fact: the sphere is the only surface with constant curvature and no boundary, so every geodesic behaves identically and there is nothing to distinguish one azimuth from another.

Break the constancy by any amount and all three fail together. Geodesics no longer close after one circuit, so the return to the starting meridian is no longer a return to the starting point; the distance to the far side depends on the route; and the family of routes from P fans out instead of reconverging. The ellipsoid breaks it by a third of a per cent and the consequences are measured in tens of kilometres.

This is the reason the cut locus is a good measurement to have made rather than a curiosity: it is a quantity that is exactly degenerate on the model everybody computes with and generically non-degenerate on the body everybody lives on, and the size of the difference is the flattening times the journey.

What was computed, and how #

The geodesics are integrated with fourth-order Runge–Kutta on the geodesic equations for a surface of revolution, 3,000 steps over up to 21,000 km, with the path sampled at about two hundred points so the crossing of the antipodal meridian can be bracketed. The bracket is then closed by forty bisections on the arc length, each of them a fresh integration, which puts the meeting point well inside a metre.

The sphere is the control and it had to pass first. Run with the flattening set to zero and everything else identical, the meeting latitudes spread over 1.6 × 10⁻⁷ degrees — about two centimetres — and every one of them is the antipode to the same accuracy. If the machinery had reported an arc there, the arc on the ellipsoid would be a property of the integrator rather than of the body.

The one thing not established here is that the meeting points found are the first time each geodesic stops being minimising. For the mirror-image pair on a body of revolution it is, by the symmetry: the two paths are each other’s reflection and neither can be beaten by the other before they meet. Whether some third geodesic beats both earlier is a question the construction does not answer, and on an oblate ellipsoid it does not arise — but the argument for that is a theorem rather than a measurement, and it is cited rather than made.

Where the model stops #

Oblate bodies of revolution only. The mirror-image construction needs the surface to be symmetric about the meridian through the starting point, which every body of revolution is. A triaxial body is not, and its cut locus is a genuinely two-dimensional problem that this method cannot touch.

And it is a cut locus of the surface, not of the terrain. Every route in this essay is on the reference ellipsoid, which is a fitted shape rather than the Earth. A route over ground has an entirely different notion of shortest, which the ladder has already met in the essay on going round an obstacle, and its cut locus is a much larger and messier set.

The arc is the mirror-pair locus, which for this body is the whole cut locus and need not be in general. On an oblate ellipsoid the two are the same set, and the argument for that is a theorem about the structure of its geodesics rather than anything measured here. On a surface with a more complicated geodesic flow the mirror pairs are a subset, and finding the rest needs a genuinely two-dimensional search.

The prolate case is not measured. For a prolate spheroid the same construction runs and the answer is different in kind — the cut locus of a non-polar point includes a segment of the equator rather than of the antipodal meridian. Mars, Jupiter and the Earth are all oblate, so the case is not idle curiosity but it is not measured here either.

The generalisation #

Uniqueness is a property of a problem, not of a solver, and a solver asked an ill-posed question will still return an answer. That is the transferable sentence, and the cut locus is the cleanest example of it this collection has: a smooth, ordinary, well-behaved minimisation whose solution set is a point almost everywhere and two points on a curve of positive measure.

The pattern recurs wherever a shortest path is computed on a curved thing. A geodesic on any Riemannian manifold has a cut locus, and the injectivity radius — the distance beyond which a geodesic may stop minimising — is one of the standard quantities used to describe how the manifold is shaped. The same object appears in optics as the caustic, where rays that left together arrive together and the ray description breaks down; and in Voronoi diagrams as the boundary, which is the cut locus of a discrete set of sites.

What cartography contributes is the arithmetic: an actual body, an actual flattening, and an actual number of kilometres, on the surface everybody’s coordinates are on.

There is a second habit worth taking away, and it is about the control rather than the result. The sphere was run first, with the same integrator, the same bisection and the same tolerance, and it returned a point to two centimetres. Only after that does an arc on the ellipsoid mean anything — because the alternative explanation for an arc, that the integrator is spreading the answers, is exactly the explanation the control eliminates. A degenerate case that the method reproduces as degenerate is the cheapest evidence available that the non-degenerate answer is about the world.

Who found it, and when #

Clairaut’s relation for geodesics on a surface of revolution dates from 1733 and is the tool that makes any of this tractable. Jacobi worked out geodesics on the triaxial ellipsoid in 1839, in one of the most celebrated integrations of the nineteenth century, and the oblate case had already been reduced to quadratures.

The cut locus is Poincaré’s, from 1905, under the name ligne de partage; Whitehead named it in 1935. The observation that a non-polar point on an oblate ellipsoid has a cut locus that is an arc rather than a point is a consequence of the structure of its geodesics and is stated in the geodesy literature — Karney’s 2013 paper on geodesics gives the relevant behaviour explicitly, together with the algorithm that computes distances reliably where Vincenty’s does not.

Thaddeus Vincenty published his iterative solutions in 1975 in Survey Review, and they are still what most software uses. His own paper notes the failure to converge for nearly antipodal points and proposes a workaround; that footnote is the cut locus, discovered from the inside by somebody trying to make an algorithm terminate.

Three discoveries of one fact #

The cut locus in this essay has been arrived at three times by three routes, and setting them side by side says something about how a geometric fact becomes known.

By construction. Poincaré defined it in 1905 as part of a study of geodesics on convex surfaces, from the inside of the mathematics, with no application in view and no computation performed.

By navigation. A sailor observing that any great circle serves to reach the far side of the world has stated the sphere’s degenerate case exactly, without a name for it and without needing one — the fact is operationally useful and the generalisation is not.

By failure. Vincenty, writing an iteration in 1975, found that it would not terminate for certain inputs and recorded the fact in a footnote with a workaround.

The three are the same fact and none of them could have been derived from either of the others. The navigator’s version is about the sphere and does not survive flattening; the algorithmic version is about one iteration and reads as a numerical defect; the mathematical version is general and says nothing about which inputs a practitioner will meet.

What makes the collection of them worth having is that each supplies what the others lack — the generality, the operational meaning, and the specific inputs on which it bites — and a subject that holds all three is in a better position than one that holds any of them alone.

Vincenty’s footnote deserves a moment of its own, because of how the discovery arrived. He was not investigating the cut locus; he was writing an algorithm and finding that it would not terminate for certain inputs, and the non-termination is the geometry announcing itself through the arithmetic. A quantity with two answers has no fixed point for an iteration to converge to, so the iteration wanders — which is the same information Poincaré’s construction carries, arriving as a practical nuisance rather than as a theorem, seventy years later and to somebody who was not looking for it. Numerical failure is an underrated instrument: an algorithm that will not converge is often reporting something true about its subject rather than something wrong about itself.

The pattern is worth watching for elsewhere: a persistent numerical failure in a well-written algorithm is a hypothesis about the problem rather than a bug report about the code.

Reading it the other way — patching the symptom, raising the iteration limit, clamping the input — costs whatever the geometry was trying to say.Reading it the other way costs whatever the geometry was trying to say.

Where the ladder goes next #

This rung is about a place where the geometry has two answers. The screen ladder has a different kind of ambiguity to face: it has spent six essays treating a vector tile as geometry that survives being zoomed, and a vector tile’s coordinates are integers on a lattice that is a different size at every level.