Slashdot Mirror
The Longest Straight Path You Could Travel On Water Without Hitting Land (gizmodo.com)
An anonymous reader quotes a report from Gizmodo: Back in 2012, a Reddit user posted a map claiming to show the longest straight line that could be traversed across the ocean without hitting land. Intrigued, a pair of computer scientists have developed an algorithm that corroborates the route, while also demonstrating the longest straight line that can be taken on land. The researchers, Rohan Chabukswar from United Technologies Research Center Ireland, and Kushal Mukherjee from IBM Research India, created the algorithm in response to a map posted by reddit user user kepleronlyknows, who goes by Patrick Anderson in real life. His map showed a long, 20,000 mile route extending from Pakistan through the southern tips of Africa and South America and finally ending in an epic trans-Pacific journey to Siberia. On a traditional 2D map, the path looks nothing like a straight line; but remember, the Earth is a sphere.
Anderson didn't provide any evidence for the map, or an explanation for how the route was calculated. In light of this, Chabukswar and Mukherjee embarked upon a project to figure out if the straight line route was indeed the longest, and to see if it was possible for a computer algorithm to solve the problem, both for straight line passages on water without hitting land or an ice sheet, and for a continuous straight line passage on land without hitting a major body of water. Their ensuing analysis was posted to the pre-print arXiv server earlier this month, and has yet to go through peer review. "There would be 233,280,000 great circles to consider to find the global optimum, and each great circle would have 21,600 individual points to process -- a staggering 5,038,848,000,000 points to verify," the researchers wrote in their study.
Anderson didn't provide any evidence for the map, or an explanation for how the route was calculated. In light of this, Chabukswar and Mukherjee embarked upon a project to figure out if the straight line route was indeed the longest, and to see if it was possible for a computer algorithm to solve the problem, both for straight line passages on water without hitting land or an ice sheet, and for a continuous straight line passage on land without hitting a major body of water. Their ensuing analysis was posted to the pre-print arXiv server earlier this month, and has yet to go through peer review. "There would be 233,280,000 great circles to consider to find the global optimum, and each great circle would have 21,600 individual points to process -- a staggering 5,038,848,000,000 points to verify," the researchers wrote in their study.
curvature of the Earth
Or you could use a nice globe and a piece of string.
If you think I voted for Trump because of this post, you're wrong. I voted for Dr. Jill Stein of the Green Party. Again.
is as far as it could ever be. This is well documented, and has been for more than a century.
% that bitch and BAM! Traveling Salesman Problem solved!
It took me a few seconds to see how the path shown on the map is straight. Sure, straight lines on the Earth will look curved on a map, but that path heads very much South, then turns and heads very much North. How can that possibly be straight?
Then it dawned on me. If you're near the South Pole and you head South, toward the pole, then keep going PAST the South Pole, you'll be headed North - all the while going straight.
Where the path goes South of South America, it's near the pole. What looks like a turn North is actually going straight across Antarctica and up the other side.
If you get Tardchris out of the water, the world's sea level will drop by a few inches, changing the results.
It is the longest path along a geodetic line. Not a straight in 3-D space.
Huh? If you look at TFA, the line clearly has an endpoint on the western edge of the Indian subcontinent, and does not approach western Europe at all..
Wouldn't 5 trillion comparisons take only about 2000 seconds on a modern processor, even without multithreading or SIMD optimizations?
Man, some people will do *ANYTHING* to avoid Russia!
I should have said the path goes "straight past Antarctica", rather than "straight across Antarctica".
As you head South, as you pass Antarctica you're suddenly heading North, without ever turning.
The longest great circle route they found on land is like the one Christopher Priest used in his science fiction story Inverted World in 1974. Perhaps it's obviously the longest route when you spend some time poring over a globe.
// DevsVult: The Machines Will It
"The path covers an astounding total angular distance of 2883523, for a distance of 32 089.7 kilometers.
This path is visually the same one as found by kepleronlyknows, thus proving his assertion."
Technically, you cannot travel in a straight line for ANY distance on the surface of a sphere, right?
At best you can have a single point of tangency.
I mean, come on, if you're going to be pedantic, let's really be pedantic!
Comment removed based on user account deletion
Why the focus on straight lines, why not study gay lines as well? There are plenty of clubs in San Francisco that have gay lines outside them to study.
Wow, great job understanding a fucking sphere bro! #There is hope for Republicans?
What else, besides mental weight lifting, could this information be used for besides impact trajectory.
Try 13,620 km Sierra Lieone to ZhangZhou I think their program need tweaking. See Google Earth
The memories of a man in his old age are the deeds of a man in his prime - Floyd, Pink
Remember when they used to call this programming?
Evolution: Programmer->Software Engineer->Algorithm Developer->Software Algorithmnist
News for nerds and/or stuff that matters, perhaps?
The algorithm being the nerdy stuff here.
Also, the "news for nerds, stuff that matters", no longer mentioned near the /. logo.
A lot of factors will deviate any ship as it travels on the ocean between point A and B, I remember when a friend of mine who's a nautical engineer showed me how many calculations it takes to adjust course due to deviation from the wind alone.
Now that I have read the actual article, several crucial simplification stand out:
a) All calculations are done assuming a perfectly spherical Earth.
b) The ETOPO1 data set has quite limited resolution, using data from (say) Google Earth or OpenStreetMap would probably give significantly better positioning of the actual coast lines. Having looked at both of them for the starting point in Pakistan it seems like you can at least get to a sub-5 m resolution for that coast.
I strongly recommend trying this in Google Earth, since that model will allow you to tilt and rotate the Earth so that the given path actually becomes a straight line and you can roll the Earth on your screen all the way from start to finish!
However, the algorithm they chose to use is still quite reasonable, i.e. relaxing the coast lines to get a fast way to discard most possible paths very easily, and then doing more exact calculations on the remaining possibilities. Since the errors caused by using a spherical model are well within the coastline relaxation offsets, you should be able to use their approach to get candidate paths and then micro-adjust them using a more accurate geodetic model. At this point you could also use Google Earth to trace a much more accurate coast line for the most important locations, i.e. around the end points and the tangential touches along the African and South American coast.
Terje
"almost all programming can be viewed as an exercise in caching"
If you take a constant heading as "straight", circling the greater Southern Ocean area below South America and above Antarctica, accumulating a minute of deviation each circuit, you could get over 100,000 miles...
That's 180 x 60 x 60 x 180 x 2. Now, I get the 180 x 60 x 60 part: It's 180 degrees of latitude (-90 to 90) of 60 minutes of 60 seconds. I get the 180 degrees of longitude, a coarse granularity but still useful. But why the 2? Surely a great circle at 20 Lat. 60 Long. will equal a great circle at -20 Lat. -120 Long.; so there's no point using every longitude?
Also, Lat. 90 and Lat. -90 are on the same great circle for each longitude (thus, forming a meridian). To stop counting that twice, should the solution be (180 x 60 x 60 - 1) x 180 x the-rest?
Yes - the longest _land_ route, which the article is about, does have one end near Sagres, Portugal, but the quoted text is describing the longest sea route.
rant
If you look at TFA (Figure 9), the longest straight line that can be taken *on land* indeed starts in Portugal. You're both correct.
Have you never seen orbital plots for satellites and spacecraft? They look the same.
There is a straight path but it is just a lot shorter. The oceans have a depth so you can travel in a straight line through them but it is going to be a lot shorter than 32,000 km.
This is obvious for anyone who had taken any long distance flight in the past decade or two.
The flight path are often shown in cycles, showing both 2D map view which you see the curved lines, and also the spherical view which made the flight path more obviously a straight line.
Not really.
I would think that drawing a line on a circle would not be hard. All you now need to do is make weg or of all the land and see if that line hits land or not. Something that has been done in Space Duel and any other duelling game.
You could even show an explosion, like in the games.
Don't fight for your country, if your country does not fight for you.
In spherical geometry:
That last one is the rule you've come across.
Is that because he drives a car and Patrick Anderson walks?
Confucius say, "Find worm in apple - bad. Find half a worm - worse."
"There would be 233,280,000 great circles to consider to find the global optimum, and each great circle would have 21,600 individual points to process -- a staggering 5,038,848,000,000 points to verify,"
Yeah, right. Technically there are an infinite number of great circles and of points. Though I suppose to the nearest minute of angle is probably going to get you close (360x60 = 21600, hence that appears to be their unit of measure).
Yes - the longest _land_ route, which the article is about, does have one end near Sagres, Portugal...
Not to be pedantic, but the subject of the article is the algorithm.
...but the quoted text is describing the longest sea route.
Exactly. The original AC is complaining about the summary saying "Pakistan" instead of "Portugal" -- like it's a typo. The subject of that sentence in the summary is the sea route, as you said. So Pakistan is correct, not Portugal.
The AC is complaining about a line in the summary discussing the sea route, though.
I don't think these researchers dug deep enough into the history of this. For those who are interested, here is the reddit post:
https://www.reddit.com/r/MapPorn/comments/15mwai/the_longest_straight_line_you_can_sail_almost/
Here's another reddit thread that he cross-posted to from five years ago; it seems that the researchers didn't dig deep enough:
https://www.reddit.com/r/todayilearned/comments/15mxxp/til_you_can_sail_almost_20000_miles_in_a_straight/
Apparently he learnt it from a Wikipedia article, where it is also reported (without citation) that the longest distance only on land is 13,573 km (8,434 mi).
The edit was added with this revision by Wikipedia user Muh1974 (who doesn't have a Wikipedia user page). The Talk page around that time has unreferenced "I remember reading somewhere" speculation about the longest great circle. My guess is that Muh1974 checked (somehow) that this path was valid, and had a distance at least comparable to the other ones mentioned in the wikipedia article, but that's where the trail goes cold for me.
Ask me about repetitive DNA
...calculated using the right metric for your space.
How do you explain latitudinal lines?
I guess you're more correct, then. :)
Lines of latitude aren't straight.
All I want is a secure system where it's easy to do anything I want. Is that too much to ask ~~ Randall Munroe
Lines of latitude aren't straight.
What'll really bake your noodle is that no line is ever straight due to the curvature of space...
We'll make great pets
In spherical geometry, parallel *STRAIGHT* lines always cross. In spherical geometry, except for the equatorial line, all latitudinal lines are curved.
If the north pole is clear of ice can you make it through the Bering Straight in a straight line that would go from Antarctica to Antarctica? Up the Pacific and down the Atlantic?
My other solution would be to be a looping straight line between the tip of South America and Antarctica, you would have a shorter run but after a couple of times around the world you might get to more than 20,000 miles.
Calvin:Do you believe in the devil? Hobbes:I'm not sure man needs the help.
"... was possible for a computer algorithm to solve the problem, both for straight line passages on water without hitting land or an ice sheet, and for a continuous straight line passage on land without hitting a major body of water."
Um... from a mathematical point of view, why would it be different searching for the longest uninterrupted straight line on land versus water? Does the maths work different if the stuff you're going over is green on the map rather than blue?
What a fucking stupid thing to say.
It is not Siberia!
The orbits of celestial bodies are strait lines through the curvature of space.
The thing that baked my noodle was realizing that gravity was like centrifugal force. When spinning, you feel pushed to the outside, but the real force is the centripetal force keeping you from flying outward as your inertia wants to. Likewise, on earth you feel drawn to the center, but the real force is the earth pushing you upward preventing you from travelling in a "straight line" to the earth's center as your inertia wants you to (due to the earth's gravity warping space-time in that way).
What's up with all of the extra lakes on the map? I didn't know there was a massive lake in the middle of Greenland.
If you have a submarine, you could go under the north pole.
Read this...
"posted by reddit user user kepleronlyknows, who goes by Patrick Anderson in real life"
I believe this is the first time I have seen in writing where a person is secondly referred to as their given name.
For some reason the fact the author to write, "who goes by" really gets under my skin.
We truly are moving toward a more individually isolated society. Even as a tech professional who does spend a good amount of time online this really bugs me.
I'm surprised this even needed to be explained on Slashdot.
Can't you just go round and round off the coast of Antarctica and never hit land, making the longest path "how ever long you want it to be?" ?
Use the property that (All == true) is equivalent to Not (Any == false).
Let's say we have polygons for the land masses (this obviously already exists, get coords online). If any random point is situated within, this invalidates the whole 21600-point line. A few minutes of this and now you have a trillion points less to check!
Optimizing this might be interesting. Sorting points by x,y would make many algorithms possible.
For example, lower precision could be used to exclude the easy cases: just remove points that are within a certain distance of another (but not if a border is within that distance, to be safe). Maybe a few trillion points less to check!
After that, you increase precision. Notice that you can still keep the results already found for the original points (they have been checked; the lower precision is that those around them have not). Therefore no check is wasted by going from low to high precision! In a way, it's like taking a huge shortcut by coloring the globe with "fat lines" if they'll cross well within borders of a land mass, and only then worrying about the small gaps remaining close to borders.
-- Danny
I'm not really a space nerd, so no, I don't look at satellite tracks on 2D maps. I'm a computer nerd, a time nerd, and a few other things, but not a space nerd.
It DOES make sense after you think about it for a minute, or if you're uses to seeing that.
Why does it need to be a Great Circle route? A Great Circle route is a route that follows an arc of a circle whose origin is the center of the Earth. But if I plot a course to follow a line of Longitude such that I drive around Antarctica, I've followed a straight path but just not a Great Circle route. There's other non-Great Circle routes that go at an angle, the only key is where the origin is of the circle. On top of that, limiting to just Great Circle routes make the additional fallacious assumption that the Earth is a sphere, when it's actually an oblate spheroid: it bulges at the Equator, so the Great Circle that is the Equator is actually larger than a Great Circle that passes through the poles. (For clarity: it's really really close to a sphere, but they're looking for extremes so it matters.)
Not saying the solution won't be a Great Circle route - It likely will be, since that's the theoretical biggest possible straight line. But there's no reason is *has* to be.
weylin
67.5% Slashdot Pure I guess I need to work on that....
In Mother Russia, globe circles you.
Bob Stein, http://bobste.in
That depends which angle you look at them from, doesn't it?