“While they were at it, they found the longest straight path you could drive without hitting water.
Back in 2012, a curious debate emerged on the discussion website Reddit, specifically on a subreddit called /r/MapPorn. Here the user Kepleronlyknows posted a map of the world purporting to show the longest navigable straight-line path over water without hitting land. The route began in Pakistan and followed a great circle under Africa and South America until it hit eastern Russia.
The post generated huge debate, with much head-scratching and pawing over charts and globes. The big question was whether the claim was correct—could there be a different straight-line route over water that was longer but uninterrupted by land of any kind? At the same time, same question arose for land—what was the longest straight-line route uninterrupted by lakes or seas?
For cartographers, it is clear that the answers would have to follow a great circle: an arc along one of the many largest imaginary circles that can be drawn around a sphere. Great circles always follow the shortest path between two points on a sphere. But how to find the great circles that contain the solutions?
We now have an answer thanks to the work of Rohan Chabukswar at the United Technologies Research Center in Ireland and Kushal Mukherjee at IBM Research in India. These guys have developed an algorithm for calculating the longest straight-line path on land or sea.
One way to solve this problem is by brute force—measuring the length of every possible straight-line path over land and water. This would be time-consuming to say the least. A global map with resolution of 1.85 kilometers has over 230 billion great circles. Each of these consists of 21,600 individual points, making a total of over five trillion points to consider.
But Chabukswar and Mukherjee have developed a quicker method using an algorithm that exploits a technique known as branch and bound.
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.
“The algorithm returned the longest path in about 10 minutes of computation for water path, and 45 minutes of computation for land path on a standard laptop,” say the researchers.
It turns out that Kepleronlyknows was entirely correct. The longest straight-line path over water begins in Sonmiani, Balochistan, Pakistan, passes between Africa and Madagascar and then between Antarctica and Tierra del Fuego in South America, and ends in the Karaginsky District, Kamchatka Krai, in Russia. It is 32,089.7 kilometers long.
“This path is visually the same one as found by kepleronlyknows, thus proving his [sic] assertion,” say Chabukswar and Mukherjee.
The longest path over land runs from near Jinjiang, Fujian, in China, weaves through Mongolia Kazakhstan and Russia, and finally reaches Europe to finish near Sagres in Portugal. In total the route passes through 15 countries over 11,241.1 kilometers.
The question now is: who will be the first to make these journeys, when, and how?
Ref: arxiv.org/abs/1804.07389 : Longest Straight Line Paths on Water or Land on the Earth”