Shortest Path in Plane - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T09:40:24Z http://mathoverflow.net/feeds/question/66990 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/66990/shortest-path-in-plane Shortest Path in Plane andy 2011-06-05T21:49:56Z 2011-06-06T12:59:51Z <p>Hi</p> <p>I thought about the following problem:</p> <p>Given a polygonal subdivision of the euclidian plane where each of the polygons has a speed associated with it, and given two points s,t, I'm interested in the fastest path from s to t.</p> <p>I don't know if the problem is NP-hard or not. If the regions are convex, I have an easy 2-approximation algorithm. (Maybe there is an PTAS algorithm for the convex/general case?)</p> <p>I'm pretty sure that this problem has been studied before.</p> <p>Does anybody know any publications about it and/or has an idea how to show NP-hardness. (But after all, maybe the problem is easy.)</p> <p>Thank you</p> <p>Andy</p> http://mathoverflow.net/questions/66990/shortest-path-in-plane/66992#66992 Answer by Yuri Bakhtin for Shortest Path in Plane Yuri Bakhtin 2011-06-05T22:19:55Z 2011-06-05T22:47:14Z <p>In this generality, the shortest path is not necessarily well defined, i.e., it can happen that the minimum is not attained, approximations to the minimizer being paths going further and further away to infinity.</p> <p>Hence, no algorithm is guaranteed to terminate correctly in finite time.</p> http://mathoverflow.net/questions/66990/shortest-path-in-plane/66997#66997 Answer by maproom for Shortest Path in Plane maproom 2011-06-05T23:03:59Z 2011-06-05T23:03:59Z <p>The speed in each polygon is a constant, so a locally fastest path will be "refracted" at each boundary using Snell's law. This doesn't answer the question, but it may cut down the calculations.</p> http://mathoverflow.net/questions/66990/shortest-path-in-plane/67004#67004 Answer by Chris Elion for Shortest Path in Plane Chris Elion 2011-06-06T00:24:59Z 2011-06-06T00:24:59Z <p>Without loss of generality, let's assume the polygons are triangles; if not, you can covert them to triangles with e.g. ear-clipping.</p> <p>A good approximation to the shortest path is to do a standard Dijkstra search, using the midpoints of edges as the "nodes" in the graph, and the cost as the Euclidean distance between midpoints weighted by 1/velocity. A* would also work, but you'd have to be careful about the heuristic - you'd probably have to h = (Euclidean distance / max velocity).</p> <p>Some other references that might deal with the "exact" problem:</p> <blockquote> <p><strong>Fast exact and approximate geodesics on meshes.</strong> V. Surazhsky, T. Surazhsky, D. Kirsanov, S. Gortler, H. Hoppe. ACM Trans. on Graphics (SIGGRAPH), 24(3), 2005. <a href="http://research.microsoft.com/en-us/um/people/hoppe/geodesics.pdf" rel="nofollow">http://research.microsoft.com/en-us/um/people/hoppe/geodesics.pdf</a></p> </blockquote> <p>and </p> <blockquote> <p><strong>Theta*: Any-Angle Path Planning on Grids.</strong> K. Daniel, A. Nash, S. Koenig and A. Felner. Journal of Artificial Intelligence Research, 39, 533-579, 2010. <a href="http://idm-lab.org/project-o.html" rel="nofollow">http://idm-lab.org/project-o.html</a></p> </blockquote> <p>I'm not sure how well the methods there will extend to the case with different weights on the polygons, but it should be a good starting point. </p> http://mathoverflow.net/questions/66990/shortest-path-in-plane/67005#67005 Answer by Joseph O'Rourke for Shortest Path in Plane Joseph O'Rourke 2011-06-06T01:12:12Z 2011-06-06T12:59:51Z <p>The problem you posed is known in the literature as the <em>weighted region problem</em>. It was the focus of Joe Mitchell's Ph.D. thesis, under the direction of Papadimitriou, and their results were eventually published in the <em>Journal of the ACM</em>: "The weighted region problem: finding shortest paths through a weighted planar subdivision," Joseph S. B. Mitchell, Christos H. Papadimitriou, <a href="http://portal.acm.org/citation.cfm?id=102782.102784" rel="nofollow">Volume 38, Issue 1, Jan. 1991</a>. As maproom noted, Snell's law applies and helps. Under the interpretation in this paper, the problem can be solved in polynomial time, $O(n^8 L)$, where $L$ reflects the input precision (assumed to be integer coordinates) and the output error tolerance $\epsilon$. Here is their abstract.</p> <blockquote> <p><b>Abstract.</b> The problem of determining shortest paths through a weighted planar polygonal subdivision with $n$ vertices is considered. Distances are measured according to a weighted Euclidean metric: The length of a path is defined to be the weighted sum of (Euclidean) lengths of the subpaths within each region. An algorithm that constructs a (restricted) “shortest path map” with respect to a given source point is presented. The output is a partitioning of each edge of the subdivion into intervals of $\epsilon$-optimality, allowing an $\epsilon$-optimal path to be traced from the source to any query point along any edge. The algorithm runs in worst-case time $O(ES)$ and requires $O(E)$ space, where $E$ is the number of “events” in our algorithm and $S$ is the time it takes to run a numerical search procedure. In the worst case, $E$ is bounded above by $O(n^4)$ (and we give an $\Omega(n^4)$ lower bound), but it is likeky that $E$ will be much smaller in practice. We also show that $S$ is bounded by $O(n^4L)$, where $L$ is the precision of the problem instance (including the number of bits in the user-specified tolerance $\epsilon$). Again, the value of $S$ should be smaller in practice. The algorithm applies the “continuous Dijkstra” paradigm and exploits the fact that shortest paths obey Snell's Law of Refraction at region boundaries, a local optimaly property of shortest paths that is well known from the analogous optics model. The algorithm generalizes to the multi-source case to compute Voronoi diagrams.</p> </blockquote> <p>Here is their Fig. 4, illustrating that the shortest path between two points $x$ and $x'$ within one region $f$ is not always the segment $x x'$: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/MitchellFig4.jpg" alt="Fig 4"></p>