Computer scientists discover longest line you can sail without hitting land
Source: Shane McGlaun
An argument that started on Reddit years ago has finally been settled. The argument had to do with finding the longest straight-line path that you could sail around the world without hitting land. One glance at the images here and it’s clear that these paths aren’t a straight line.
Keep in mind that the arc is a representation of the straight-line on the spherical surface of the Earth represented on a flat map. Rohan Chabukswar from United Technologies Research Center in Ireland and Kushal Mukherjee from IBM Research in India have developed an algorithm that can calculate the longest straight-line path on sea or land. The duo has presented their work.
The algorithm uses a technique called branch and bound. This works by looking at all potential solutions as branches on a tree. The algorithm then checks one branch after another. Bounding comes in to reduce the workload that branching requires alone. It essentially looks at the possible solutions in a branch and tries to find the one subset closer to the optimal value.
If the branch isn’t close to the optimal solution, it is ignored entirely. The two researchers said that their algorithm returned the longest water path in about ten minutes of computation. The longest path for land took longer to find needing 45 minutes. Both paths were found with the algorithm running on a normal laptop.
Interestingly the water path is “virtually” the same one that reddit user kepleronlyknows had found in his original claim of finding the longest path back in 2012. The path the researchers charted is 32,089.7 km long. The longest land path runs through 15 countries and spans 11,241.1km.
| }
|