As the Crow Flies: The Longest Navigable Line

Two researchers mathematically prove the longest navigable straight path on earth.

By Brian K. Lind

May 10, 2018

If you set off in your boat, what is the furthest you could sail in a single straight line? And how does one figure out with certainty that the path is an actual straight line? Back in 2012, a Reddit user by the name of KeplerOnlyKnows (which, side note, is a great handle for being a planetary map geek) posted what he believed was the longest possible straight line one could sail on the Reddit thread /MapPorn (for those concerned potential vulgarity, there is no nudity involved here, other than the laying bare of cartographic philosophies). The user posted the image seen below, but the only proof he provided was a video he created using Google Earth after some Reddit users disputed how a curved line on his map could be considered “straight.” (Flat-earthers can read my note at the bottom of this article.)

Redditors have debated the findings of KeplerOnlyKnows and several other map enthusiasts have proposed both the longest straight line one could navigate by both sea and by land. This problem gained the interest of Rohan Chabukswar at the United Technologies Research Center in Ireland and Kushal Mukherjee at IBM Research in India. While in many ways this was a recreational problem, the two set out to figure out a mathematical system to figure out what the longest navigable (and drivable lines) on earth actually are.

The key to understanding their approach lies in understanding the concept of great circles, which are the number of circles on a sphere that pass through the sphere’s center. The shortest distance between two points on a sphere is always found on a great circle. Now, one solution to this is just “brute force,” sitting down and trying all the likely great circles one thinks have possibility, and Chabukswar and Mukherjee considered that. But the algorithm they figured out was much more brilliant (and I’m not even sure I totally understand it).

Chabukswar and Mukherjee utilized a free dataset from NOAA known as ETOPO1 Global Relief model of Earth’s surface. As they explain:

ETOPO1 is a 1 arc-minute global relief model of Earth’s surface that integrates land topography and ocean bathymetry. It was built from numerous global and regional data sets, and is available in “Ice Surface” (top of Antarctic and Greenland ice sheets) and “Bedrock” (base of the ice sheets) versions. The version suited for this problem was the “Ice Surface” one, since a sailable path should not hit an ice layer, and technically ice could be driven upon.

This dataset provided 233,280,000 great circles, with each circle providing 21,600 data points (based on the resolution of ETOP01), which provided 5,038,848,000,000 data points to process. That’s quite a few.

So how does one process over five trillion data points? With a computer algorithm of course! And that is what is unique to this process … well, for the math geeks out there, anyway. For the rest of us sailors you need to imagine sailing along a nearly 20,000-mile-long path (19,939.6 miles, 4,961.4 miles shy of the earth’s total circumference). By utilizing what is called a branch-and-bound algorithm they were able to crunch the data for the seagoing route in ten minutes on a common laptop. While I could try to describe how this algorithm works, I’d just be paraphrasing this explanation from Technology Review on Chabukswar and Mukherjee’s findings:

This works by considering potential solutions as branches on a tree. Instead of evaluating all solutions, the algorithm checks one branch after another. That’s called branching, and it is essentially the same as a brute-force search. But another technique, called bounding, significantly reduces the task. Each branch contains a subset of potential solutions, one of which is the optimal solution. The trick is to find a property of the subsets that depends on how close the solutions come to the optimal one. The bounding part of the algorithm measures this property to determine whether the subset of solutions is closer to the optimal value. If it isn’t, the algorithm ignores this branch entirely. If it is closer, this becomes the best subset of solutions, and the next branch is compared against it. This process continues until all branches have been tested, revealing the one that contains the optimal solution. The branching algorithm then divides this branch up into smaller branches and the process repeats until it arrives at the single optimal solution. The trick that Chabukswar and Mukherjee have perfected is to find a mathematical property of great-circle paths that bounds the optimal solution for straight-line paths. They then create an algorithm that uses this to find the longest path.

In the end what Chabukswar and Mukherjee found was that KeplerOnlyKnows was right all along, at least visually. Their lines differ slightly in terms of mathematics/great circle. (Click here to read their full paper, it is surprisingly brief and interesting).

So the only question that is left is not one that can be solely decided by computers and algorithms (although they would probably help). Is it possible for someone to sail this path from Sonmiani, Las Bela, Balochistan, Pakistan (25◦170 N, 66◦400 E) to Karaginsky District, Kamchatka Krai, Russia (58◦370 N, 162◦140 E)? How quickly can it be done? And can it be done single-handed? Personally I’m not all that interested in finding out (or planning the logistics), however I do find the path across the earth fascinating and I’m glad someone took the time to figure it out.