A route that must go round

The shortest path between two places on a sphere is an arc of a great circle. Every route essay on this site so far has taken that as the end of the geometry and gone on to what a map does with it.

No real route has that freedom. There is closed airspace, a country that will not grant an overflight, a storm cell, an exclusion zone, a minefield. The question becomes the shortest path on a sphere with a disc removed, and — unlike almost everything else in this neighbourhood — it has a closed form.

The answer, and why its middle is strange #

The route is a tangent, an arc of the rim, and a tangent. Two thirds of that is unsurprising: a shortest path is a geodesic wherever it is free, and the tangency is what makes the joins smooth.

The middle third is not. The rim of the disc is not a geodesic, so a path following it is not locally shortest anywhere along that stretch — at every point of it there is a nearby shorter path, and every one of those goes inside the disc. The constraint is doing the work, and the shortest admissible path is made partly of a curve that is shortest for nothing.

That is the general shape of a constrained shortest path and it is worth seeing in a case small enough to compute exactly: free arcs joined by stretches that ride the constraint.

The trigonometry is a right-angled triangle #

Let $d$ be the angular distance from a point to the disc’s centre and $\rho$ the disc’s angular radius. The tangent from the point touches the rim at a right angle to the rim’s own radius, so there is a right spherical triangle with legs $\rho$ and $t$ and hypotenuse $d$, and two of Napier’s relations finish it:

$$\cos d = \cos\rho\,\cos t, \qquad \cos\theta = \frac{\tan\rho}{\tan d}$$

The first gives the tangent length, the second the angle at the centre between the direction of the point and the direction of the tangency. Doing that at both ends and taking whichever way round the rim is shorter gives the whole route.

For the case above: the tangent from London is 3,384 kilometres, the tangent from Tokyo is 5,921, and the rim between the two tangent points subtends 10.16° at the disc’s centre, which is 292 kilometres of arc at that radius. Total, 9,598.

The check that makes it a measurement #

A closed form with a plausible derivation is exactly the kind of thing this site does not print without a second route to the same number.

The second route is a shortest-path search that has never heard of tangents. Sample the rim at 360 points; add the two endpoints; join every pair of nodes by the great circle between them; discard any segment that cuts the disc; join consecutive rim points along the rim; run Dijkstra.

It returns 9,598.110 kilometres against the closed form’s 9,598.113 — a difference of three metres in 9,598 kilometres, which is the rim’s own polygonal discretisation. The optimiser was free to find something better and did not.

What it costs, and the cost is not the obstacle’s size #

The obvious guess is that a bigger obstacle costs more, in proportion. It does not, in either respect.

The quantity the cost actually depends on is the intrusion: how far the disc reaches past the route, measured from the route to the far side. Fitted over nine radii, the extra distance goes as the square of it, at an exponent of 2.01.

A quadratic law has a practical reading that a linear one would not. The first hundred kilometres of intrusion are nearly free and the last hundred are not, so an exclusion negotiated down from 20° to 18° saves 76 kilometres while one negotiated from 13° to 11° saves 10. Where the boundary is drawn matters most where it is already deepest.

What the closed form buys over the obvious detour #

The quadratic law can be given its constant, and doing so measures what the tangent-arc-tangent construction is worth against the detour anybody would sketch.

A path forced to pass a sideways distance s from the direct route, at a fraction f of the way along a route of length L, is two straight legs, and expanding both square roots gives an extra length of

$$\frac{s^2}{2L\,f(1-f)}.$$

For the worked case — 9,559 kilometres, an obstacle near the middle — that is 2s²/L, and against the six measured intrusions it gives 3.4, 25.8, 44.6, 132.6 and 447.8 kilometres where the exact construction gives 3, 22.6, 39.4, 118 and 407.

So the closed form saves between nine and thirteen per cent over the corner, and the saving shrinks as the obstacle grows. That is exactly what the geometry says it should: the exact path replaces the corner with an arc of the rim, and the arc is a larger share of the detour when the disc is large, so more of the path is riding a constraint that no V approximates.

Both numbers are worth having. The V is a one-line estimate needing nothing but the intrusion and the route’s length, and it is an upper bound — a planner using it is over-quoting the detour by about a tenth, which is the right direction to be wrong in.

Where along the route the obstacle sits, corrected #

The same expression settles the question of position, and it settles it the other way round from the intuition.

The cost carries a factor of 1/f(1 − f), which is smallest at f = ½ and grows without bound towards either end. An obstacle at a tenth of the way along costs 5.56 s²/L against 2 s²/L in the middle — nearly three times as much for the same sideways displacement — because the detour has a shorter run of free geodesic over which to make it and unmake it.

That inverts the practical advice. An exclusion near a departure or an arrival is the expensive one, and it is the one to negotiate. A disc in the middle of a long route is the cheapest place for it to be, which is the opposite of the impression a picture gives, where an obstacle in the middle looks maximally in the way.

The two effects can be told apart because they respond to different things. Moving the obstacle sideways changes s and costs the square of it; moving it along the route changes f and costs the reciprocal of f(1 − f). A planner who can move an exclusion in either direction should move it towards the middle before making it smaller, and the arithmetic says by how much: shifting a disc from a tenth of the way along to the middle is worth as much as shrinking its intrusion by forty per cent.

Whether it binds at all is a cross-track question #

Before any of the arithmetic there is a decision: does the disc block the route or not. That is a comparison between the disc’s radius and the closest the great circle comes to its centre, which is the cross-track distance and is one line of vector algebra — the angle between the disc’s centre and the plane of the great circle.

The subtlety worth stating is that the closest approach may be outside the segment. A disc beyond one endpoint can be nearer to the great circle than to the great-circle arc, and a test that used the circle would report an obstruction that is behind the traveller. The machinery projects the disc’s centre onto the plane, checks whether the foot lies between the two endpoints, and falls back to the nearer endpoint if it does not.

That is a small piece of care with a large consequence: without it, the London–Tokyo route would be reported as blocked by discs in the South Atlantic.

Where the quadratic comes from #

The mechanism is the same one behind every other quadratic on this site, and it is worth naming because it makes the law expected rather than empirical.

Near the direct route, moving the path sideways by a small distance $s$ costs an extra length proportional to $s^2$ — the first-order term vanishes, because the direct route is a stationary point of length, which is what “geodesic” means. Pushing the route sideways by the intrusion therefore costs the intrusion squared, divided by a length of the order of the route.

That is the same argument as flying a curve in straight legs, where the gap between a chorded route and the true one falls as the square of the number of legs, and the same as how small is flat enough, where a plane’s error over a patch grows as the square of the patch. All three are the second-order term of a stationary quantity.

The map to plan it on #

Drawing a great circle requires a projection on which great circles are recognisable, and drawing a tangent to a disc requires a projection on which both are recognisable at once.

It is not. A small circle on the sphere maps to a conic section on the gnomonic projection — an ellipse near the centre, a hyperbola out towards the horizon — so the disc’s image is not a disc and a tangent drawn by eye is not the tangent. The one projection that maps every circle to a circle is the stereographic, and it does not straighten great circles.

So the construction that would be exact on paper needs two different projections and there is no single sheet on which both halves are true. That is which projection is best arriving as a concrete impossibility rather than as an aphorism: the operation needs two properties, and no projection has both.

When the disc swallows an endpoint #

The construction assumes both ends are outside the disc. If one is inside, there is no admissible path at all — the destination is in the exclusion — and the machinery reports that rather than returning a number.

That sounds like a triviality and it is the case a planner actually meets: an exclusion that grows until it touches a destination. The distance to the destination does not tend to infinity as the disc approaches it; it stays finite right up to the moment the destination is enclosed, and then there is no answer. The failure is a discontinuity in feasibility rather than in cost, and it is not visible in any plot of distance against radius.

The obstacle’s position matters as much as its size #

Two discs of the same radius cost different amounts depending on where they sit along the route, and the difference is not small.

An obstacle near one end is dearer than one in the middle, and the reason is the one the closed form gives above: the sideways displacement has to be absorbed over a shorter run of free geodesic, so the same $s^2/L$ arithmetic runs with a smaller $L$ and returns a larger number. A planner with a choice of where to negotiate an exclusion should negotiate whichever sits nearest an endpoint.

How a route is actually flown, and what that does to the detour #

Nothing steers a rim. The route computed here has two smooth joins and a curved middle, and an aircraft or a ship flies a sequence of constant-heading legs between waypoints.

That last point is the practical trap in the whole construction. A route computed as tangent-arc-tangent and then chorded for flying is no longer admissible: every chord across the rim passes inside it. The fix is to compute the route against a disc inflated by the chord sagitta, which is $\rho\theta^2/8$ for a leg subtending $\theta$ — a correction of 101 metres for eight legs across the 292-kilometre arc above, and 6 metres for thirty-two.

The correction is small and its absence is not a rounding: an admissible route that becomes inadmissible when it is flown has failed at the only thing it was for. That is the same class of defect as a straight segment is a claim about a plane, where two exact endpoints joined by a straight line in the wrong plane depart from the ground they claim — here the departure is inward, across a boundary somebody drew, and the tolerance is a legal one rather than a cartographic one.

Two exclusions, and where the closed form stops #

The closed form is for one disc. Two overlapping discs merge into a shape whose boundary is two arcs and whose tangent structure has to be worked out case by case; two disjoint discs may or may not both bind, and deciding which requires trying.

The graph search has no such limit. It is the same construction — sample the boundaries, join what is visible, run Dijkstra — and it scales to any number of obstacles of any shape at the cost of an answer that is only as exact as the sampling.

So this essay has one exact result and one general method, and the exact result exists mainly to establish that the general method is right. That is the ordinary relationship between a closed form and a numerical scheme, and it is stated here because the reverse is what usually happens: a numerical answer with no closed form anywhere to check it.

What the route is not #

It is not the fastest. Wind, current and traffic all move the answer, and none of them is a closed form or a property of the sphere. This is the shortest admissible path, which is what a chart can settle.

It is not the ellipsoidal answer. The construction is spherical throughout, because the tangent relations are spherical trigonometry and there is no ellipsoidal equivalent that stays in closed form. Geodesics on the ellipsoid measures what that model costs: for a route of this length the spherical and ellipsoidal distances differ by a few tenths of a per cent, which is larger than the 0.41 per cent detour being computed here.

That comparison is the honest way to state the result’s precision. The detour is a real geometric quantity, computed exactly on a sphere, and the sphere is a model whose error over the same route is of the same order as the answer. A planner needing the number to a kilometre needs the ellipsoidal version, which is an integration rather than a formula.

What the field says here #

Every other essay in this field measures what a projection does to a route that already exists. This one computes the route, and the projection appears only at the end, when somebody has to draw it.

That ordering is the right one and it is not the usual one. A route is a fact about the ground and a constraint; it is decided before any map is chosen, by trigonometry that has no page in it. The map’s job is to show it, and the measure of a map for this purpose is whether the two things the construction needs — straight geodesics and circular discs — survive being drawn.

Neither survives on any one projection, which is a genuinely new item on the list of things the operation decides the coordinate system collects.

Where this ladder goes #

The paths ladder has taken the shortest route from a definition, through the map that straightens it, the ellipsoid that complicates it, the vertex that predicts its extreme, the chords that fly it, and the antipode where it stops being unique.

This adds the first constrained route, and the constraint is the simplest one there is. The obvious next questions are a route that must stay within range of somewhere, and a route that must avoid a region with a boundary somebody drew rather than a circle. Both are the same shape of problem — free arcs joined by boundary-riding stretches — and neither has a closed form, so the next rung is a numerical one and needs the graph search this essay built to check its own arithmetic.