Skip to Content
Computing

Computer scientists have found the longest straight line you could sail without hitting land

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?

The longest straight-line land journey on Earth.

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.

The longest straight-line sea journey without hitting land.

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

 

Deep Dive

Computing

Inside the hunt for new physics at the world’s largest particle collider

The Large Hadron Collider hasn’t seen any new particles since the discovery of the Higgs boson in 2012. Here’s what researchers are trying to do about it.

Why China is betting big on chiplets

By connecting several less-advanced chips into one, Chinese companies could circumvent the sanctions set by the US government.

How Wi-Fi sensing became usable tech

After a decade of obscurity, the technology is being used to track people’s movements.

VR headsets can be hacked with an Inception-style attack

Stay connected

Illustration by Rose Wong

Get the latest updates from
MIT Technology Review

Discover special offers, top stories, upcoming events, and more.

Thank you for submitting your email!

Explore more newsletters

It looks like something went wrong.

We’re having trouble saving your preferences. Try refreshing this page and updating them one more time. If you continue to get this message, reach out to us at customer-service@technologyreview.com with a list of newsletters you’d like to receive.