I thought about the following problem:
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.
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?)
I'm pretty sure that this problem has been studied before.
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.)
Thank you
Andy
Best Answer
The problem you posed is known in the literature as the weighted region problem. It was the focus of Joe Mitchell's Ph.D. thesis, under the direction of Papadimitriou, and their results were eventually published in the Journal of the ACM: "The weighted region problem: finding shortest paths through a weighted planar subdivision," Joseph S. B. Mitchell, Christos H. Papadimitriou, Volume 38, Issue 1, Jan. 1991. 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.
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'$: