Comment by larkeith
7 years ago
"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."
What? Is there something I'm missing here, or did they just decide to include "individual points" as an utterly useless way of inflating the difficulty of a brute-force approach?
The longest path needs to start and end somewhere along a great circle. So those individual points are needed.
The only relevant points are those that make up the coastlines - there is no need to test paths that start and/or end in the middle of sea or land.
Oh I see what you mean. Yes, I suppose it is worded that way to impress the reader with the big numbers involved, when many of them can be trivially rejected.
Coastlines are close to infinite in length (they grow inversely to the length of the measure used; idealised mathematical 'coastlines' are fractal and infinite), we can limit them by limiting the resolution.
at a 1.8 km resolution (without checking my maths) 21,000 points along a great circle is basically every 1.8km so i guess you are checking at each 1.8km if you just drove into water (or vice versa)
Your point that you only need to fail once is fair - there is a lot of boundary conditions one can apply quite quickly