A pair of researchers, one with United Technologies Research Center, the other with IBM Research, has developed an algorithm that can be used to determine the longest straight-line path over water on Earth. In their paper uploaded to the arXiv preprint server, Rohan Chabukswar and Kushal Mukherjee describe their algorithm and what it revealed.
The two researchers created their algorithm in response to a post by an unknown person on Reddit (he has been identified as Patrick Anderson)—he posted what he claimed was the longest straight-line ocean trip possible on planet Earth. Along with the post was a graphic showing the proposed direct-line route, but no evidence of how it was found. Intrigued by the proposition, the two researchers wondered how they might actually calculate such a line. They knew that it would be possible to do it using a brute force approach, which would involve measuring the length of every stretch of ocean. But that, they noted, would likely require more computer power than they had. With a global map obtained from NOAA, which offered a resolution of 1.8 kilometers, they saw that a brute force approach would entail grinding through data describing over 230 billion great circles. And that would mean analyzing trillions of individual data points—clearly too much crunching for their available computer. To reduce the amount of work, they turned to mathematics—specifically, optimization algorithms called branch and bound. Such algorithms reduce the amount of searching by assigning routes to branches which themselves hold subsets of similar routes. As the algorithm runs, subsets are analyzed and branches eliminated, winnowing the amount of data requiring analysis until the branch that holds the solution is found.
By coding and running their algorithm and imputing the map data, the researchers found it took just ten minutes for their laptop to provide an answer. Interestingly, the answer was the same given by Anderson, who reportedly got his information from an unknown Wiki post. The line runs between a point on a shoreline in Pakistan all the way to a Russian shoreline—a distance of approximately 32,089.7 kilometers.
A not-quite-random walk demystifies the algorithm
Longest Straight Line Paths on Water or Land on the Earth, arXiv:1804.07389 [math.HO] arxiv.org/abs/1804.07389
There has been some interest recently in determining the longest distance one can sail for on the earth without hitting land, as well as in the converse problem of determining the longest distance one could drive for on the earth without encountering a major body of water. In its basic form, this is an optimisation problem, rendered chaotic by the presence of islands and lakes, and indeed the fractal nature of the coasts. In this paper we present a methodology for calculating the two paths using the branch-and-bound algorithm.