The route with no shortest path

The distance between two points on the Earth is a solved problem with one exception, and the exception is not a small print item: it is a whole neighbourhood of the globe, and every point has one.

What a cut locus is #

Start at a point on a sphere and set off along a great circle. For a while, the route being followed is the shortest way to every point on it — that is what a geodesic being locally shortest means.

It does not stay that way. Beyond a certain distance the same great circle, continued, stops being the shortest route to the points on it, because going the other way round has become quicker. The set of points where that switch happens is the cut locus of the starting point.

On a sphere the cut locus of any point is a single point: its antipode. That is the same great-circle geometry the shortest route is built on, followed past the point where it stops being shortest. Every great circle through the start reaches it after exactly half a circumference, all of them at once, and beyond that they are all going the long way. That is a very special situation and it is worth naming what makes it special: the cut locus is as small as a cut locus can be, and every geodesic reaches it at the same distance.

The consequence at that point #

Between London and the point diametrically opposite it — 51.507° south, 179.872° east, in the Pacific south-east of New Zealand — there are infinitely many shortest routes.

So the question what is the shortest route from London to its antipode has no answer, in the specific sense that no unique answer exists. The question how far is it has a perfectly good one — 20,015 km on a sphere of mean radius — and the two questions come apart, which they never do anywhere else.

For a computation that distinction is the whole problem. An algorithm asked for a distance will usually get there by finding the route, and here there is no route to find.

What Vincenty does about it, which is nothing #

Vincenty’s inverse formula solves the ellipsoidal problem by iteration. It guesses the difference in longitude measured on the auxiliary sphere, computes what that implies, corrects the guess, and repeats until the correction stops mattering. On ordinary pairs it converges in three or four steps and the site’s own check finds it agreeing with an independently integrated geodesic to 29 micrometres over journeys of thousands of kilometres.

Near the antipode the iteration is a fixed-point map whose derivative approaches one, and it slows down and then stops working. Measured on the scan above, taking London as the origin:

and the successes near the edge of the failing region are expensive: 199 iterations against three or four for a pair of ordinary cities.

The single failure that persists out to ±40° is the exact antipode itself, which is in every window because every window is centred on it.

This is not a criticism of Vincenty’s formulae. It is the reason Karney published a different method in 2013 — one that solves the same problem by a route that stays well conditioned in the antipodal region — and the reason Vincenty’s own 1975 paper says so.

The ellipsoid breaks the tie, by 13 km #

An ellipsoid is not a sphere, and the perfect degeneracy is a property of perfect symmetry. So on WGS84 the routes to the antipode are not all the same length, and the amount by which they differ is measurable.

Shooting geodesics from London on a fan of azimuths and following each until it passes closest to the exact antipode:

• the route that sets off due north or due south, going over a pole, is 20,003.9 km;
• the route that sets off due east or due west, following a track that stays nearer the equator, is 20,017.0 km;
• the spread between them is 13.1 km, and the intermediate azimuths fall between.

Thirteen kilometres in twenty thousand is 650 parts per million, which is the flattening’s order of magnitude, and it says that the polar route is genuinely shorter — the Earth is smaller the way the poles lie.

The measurement uses no Vincenty at all. Each geodesic is obtained by integrating its own differential equation with a fourth-order Runge–Kutta step, which is the independent reference the site already uses to check Vincenty elsewhere, and using it here matters: the formula being described as failing cannot also be the instrument.

The control is the same calculation on a sphere of the same size, where the spread must be zero. It comes out at $2\times10^{-4}$ km, which is the integrator’s own error over twenty thousand kilometres, and having that number is what makes the 13.1 km a measurement rather than a residual.

The cut locus is no longer a point #

That 13 km spread is the visible face of a change in the geometry.

On an ellipsoid the cut locus of a point is not its antipode. It is a short arc — a segment of the curve of near-antipodal points, running roughly east–west, whose length is proportional to the flattening and to the sine of the starting latitude. Points on that arc still have two shortest routes; points near it have one shortest route and a second one only slightly longer.

So the degeneracy is not removed by the flattening, it is spread out. Instead of one point at which the problem is ill-posed there is a short curve at which it is ill-posed and a neighbourhood around it in which it is merely ill-conditioned, which is worse for a numerical method: an exact singularity can be detected and special-cased, and a region of poor conditioning has to be survived.

The 19% failure rate at ±0.6° is exactly that region being surveyed.

What a routing system actually does #

Three strategies, in increasing order of respectability.

Ignore it. The plate carrée is what happens when a default goes unexamined, and this is the routing equivalent. The antipodal region of any given place is a few tens of thousands of square kilometres of somewhere, usually ocean, and most software will never be asked. This works until it does not, and the failure mode is a NaN or a silent non-convergence rather than a wrong number.

Detect and special-case. Test whether the two points are nearly antipodal, and if they are, return the polar route or the closed-form spherical answer with a note. Correct, and it requires a threshold nobody can defend.

Use a method that does not have the problem. Vincenty’s agreement with the integrated reference is what makes it trustworthy elsewhere, and the same comparison is what exposes it here. Karney’s algorithm reformulates the iteration so that the antipodal case is well conditioned, and returns an answer accurate to nanometres everywhere including there. It is the right answer and it is what modern libraries use.

There is a fourth response worth recording because this site has a rule about it: make the failure visible. A convergence flag that can be true beside a NaN is not a flag worth having, and the version of Vincenty’s formula in this library reported exactly that until the antipodal work went in — the loop’s exit test is a comparison, NaN fails every comparison, so an iteration that goes bad on its first step exits immediately with zero iterations and a clean bill of health. Requiring the answer to be finite as well as the iteration count to be small is one line, and it converts a silent wrong answer into a reported failure.

Where it sits among the other paths #

The great-circle vertex is the highest latitude a route reaches, and Clairaut’s relation gives it in closed form. For an antipodal pair that formula degenerates too, and for the same reason: the vertex depends on the departure azimuth, and the departure azimuth is undetermined.

That gives a useful way to picture the whole situation. The family of shortest routes to the antipode is a one-parameter family indexed by the departure azimuth, and its members have vertices running all the way from the starting latitude to the pole. Every one of them is a legitimate answer, and they differ in almost every respect a navigator might care about — highest latitude, weather, whether they cross land — while being identical in the one respect the question asked about.

The projection that shows it properly #

Every figure above has to draw an infinite family of equal-length routes on a sheet that cannot represent them as equal. One projection can, and it is the one built for exactly this.

That is worth dwelling on, because it is the cleanest instance of a pattern the site keeps meeting. A projection built to represent one quantity faithfully represents the degeneracy in that quantity faithfully too: the azimuthal equidistant does not obscure the fact that the antipode has no unique direction from the centre, it draws that fact as a circle. The gnomonic’s companion property does the same in the other direction — every great circle is straight and the price is that half the world cannot be shown at all.

Every point has one #

Nothing above is about London.

Every point on Earth has an antipodal region in which the inverse problem is ill-conditioned, and its size is set by the flattening, not by the place. The one thing that does vary is how much company it has: London’s antipode is in the open Pacific, while a point in the Pacific has its antipode in central Asia, where there are considerably more pairs of places anyone might ask about.

The same phenomenon elsewhere #

A cut locus is not a cartographic curiosity; it is what makes a surface a surface rather than a plane.

On a cylinder, the cut locus of a point is the opposite generator — the straight line running along the far side — and again there are two shortest routes to each of its points, one round each way. On a cone it is a single line. On a general convex surface it is a tree-like graph, and computing it is a genuinely hard problem.

The Earth’s case is unusually clean because the surface is unusually symmetric, and the transition from sphere to ellipsoid is a small controlled step away from that symmetry. Thirteen kilometres of spread is the whole of the difference between no answer and an answer that is hard to compute.

What it costs a navigator, which is nothing #

The practical importance of all this is close to zero, and saying so is part of reporting it honestly.

A ship or an aircraft crossing to the far side of the world is not choosing between routes 13 km apart in a 20,000 km journey; it is choosing between routes that differ by thousands of kilometres in fuel, weather, airspace and diversion airports. The degeneracy that makes the geometric question unanswerable makes the practical question easier, because it means the geometry has stopped constraining the choice and everything else is free.

What the case does matter for is software. A library that returns a distance for every pair of points except a region nobody tests is a library with a bug waiting in it, and the bug surfaces as a NaN propagating into a display or a plan rather than as an error anybody can act on. The rhumb line’s excess of 18% over the great circle is the kind of cost a navigator trades against convenience; the antipodal failure is not a cost at all, it is a hole.

That distinction — between a quantity that is large and a quantity that is undefined — is one the site’s habit of measuring everything is unusually good at drawing, because a measurement that cannot be taken announces itself.

One ordinary long route, drawn on the projection that measures distance from the starting point truly, for comparison with the degenerate case.

What was computed here #

The scan drives Vincenty’s inverse formula to every target on a grid centred on the antipode, recording convergence and iteration count, at four window sizes from ±0.2° to ±40°. Two claims are asserted: it must fail somewhere within 0.6° of the antipode, which a run that reached everywhere would falsify, and it must succeed everywhere more than 30° away, which makes the failure a property of the neighbourhood rather than of the formula.

The route lengths come from integrating the geodesic equations on WGS84 with 700 Runge–Kutta steps per route, over sixteen azimuths, with the range to closest approach found by ternary search. The spread must be between 1 and 100 km on the ellipsoid, and below 0.05 km on a sphere of the same semi-major axis.

What the pictures cannot show #

The scan is a picture of an algorithm rather than of the Earth. Nothing is wrong with the sea south-east of New Zealand; what the dark cells record is the conditioning of one method at one tolerance.

The routes figure shows eight members of an infinite family and has to draw them on some projection, which means the eight look different lengths. They are not. That is the every figure is itself a projection problem in its sharpest form: a figure whose subject is that several curves have equal length, drawn on a surface where no projection can show them so.

Who found it, and when #

The cut locus was named by Poincaré in 1905, in a paper on geodesics of convex surfaces, and the antipodal degeneracy of the sphere was understood long before anyone had a word for it — a navigator who observes that any great circle will do to reach the far side of the world has stated it.

Vincenty published his formulae in 1975 for a specific practical purpose, and noted the antipodal failure in the paper. Karney’s Algorithms for geodesics of 2013 removed it, and the abstract’s claim of accuracy “including nearly antipodal points” is a direct reference to the case that had been outstanding for thirty-eight years.

Why a degeneracy nobody suffers from is worth thirty-eight years #

The cost to a navigator is nothing, and the defect nevertheless took until 2013 to remove. That combination is worth a paragraph, because it is not an oversight.

A failure at a measure-zero set is a failure a user never meets and a library always must. No voyage is planned between exactly antipodal points; every geodesic library is called with arbitrary inputs by software that did not check, and nearly antipodal is a set with positive measure that Vincenty’s iteration also handles badly. The degeneracy is unreachable in practice and its neighbourhood is not.

And the failure mode is the bad kind. An iteration that does not converge returns whatever it had, or a NaN, or a number after the iteration limit — so a caller receives a plausible distance with no indication that the algorithm gave up. That is worse than an exception, and it is what makes the case worth fixing for reasons that have nothing to do with anybody sailing there.

The reason it stood so long is that the exact case is where the mathematics is interesting and the near case is where the trouble is. Vincenty noted the exact failure and it reads as a curiosity; the useful statement is about a neighbourhood, and stating it requires knowing how the iteration degrades rather than that it fails.

Which is why Karney’s phrasing is the right one. Including nearly antipodal points is a claim about a region rather than a point, it is testable by sampling, and it is what a caller actually needs to know. A library that worked everywhere except one pair of points would be a curiosity; one that works everywhere including the neighbourhood of that pair is a library.

Where this goes next #

The other end of the paths ladder is the practical one. A geodesic is a curve, nothing can steer a curve, and what a route actually consists of is a sequence of straight pieces — which costs something measurable.