StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Assuming the map is rectangular, you can loop over all border points, and start a flood fill to find the most distant point from the starting point:</p> <pre><code>bestSolution = { start: (0,0), end: (0,0), distance: 0 }; for each point p on the border flood-fill all points in the map to find the most distant point if newDistance > bestSolution.distance bestSolution = { p, distantP, newDistance } end if end loop </code></pre> <p>I guess this would be in <code>O(n^2)</code>. If I am not mistaken, it's <code>(L+W) * 2 * (L*W) * 4</code>, where <code>L</code> is the length and <code>W</code> is the width of the map, <code>(L+W) * 2</code> represents the number of border points over the perimeter, <code>(L*W)</code> is the number of points, and <code>4</code> is the assumption that flood-fill would access a point a maximum of 4 times (from all directions). Since <code>n</code> is equivalent to the number of points, this is equivalent to <code>(L + W) * 8 * n</code>, which should be better than <code>O(n</code><sup>2</sup><code>)</code>. (If the map is square, the order would be <code>O(16n</code><sup>1.5</sup><code>)</code>.)</p> <p><strong>Update:</strong> as per the comments, since the map is more of a maze (than one with simple obstacles as I was thinking initially), you could make the same logic above, but checking all points in the map (as opposed to points on the border only). This should be in order of <code>O(4n</code><sup>2</sup><code>)</code>, which is still better than both F-W and Dijkstra's.</p> <p><em>Note:</em> <a href="http://en.wikipedia.org/wiki/Flood_fill" rel="nofollow noreferrer">Flood filling</a> is more suitable for this problem, since all vertices are directly connected through only 4 borders. A breadth first traversal of the map can yield results relatively quickly (in just <code>O(n)</code>). I am assuming that each point may be checked in the flood fill from each of its 4 neighbors, thus the coefficient in the formulas above.</p> <p><strong>Update 2:</strong> I am thankful for all the positive feedback I have received regarding this algorithm. Special thanks to @Georg for <a href="https://stackoverflow.com/questions/477591/algorithm-to-find-two-points-furthest-away-from-each-other#478076">his review</a>.</p> <p>P.S. Any comments or corrections are welcome.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload