8
$\begingroup$

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

Improve this question
$\endgroup$

4 Answers 4

Reset to default
12
$\begingroup$

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.

Abstract. 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.

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'$:
          Fig 4

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This made me remember one explanation of how can one think of the upper plane model of the hyperbolic plane, as a limit of weighted regions were the regions are cheaper as you go up. The shortest path will aproximate semi-circles. $\endgroup$
    – Gerardo Arizmendi
    Commented Aug 11, 2015 at 13:11
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Hence, no algorithm is guaranteed to terminate correctly in finite time.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Hi Yuri Could you illustrate a situation where the problem is not well defined? $\endgroup$
    – user695652
    Commented Jun 6, 2011 at 17:40
  • 3
    $\begingroup$ of course, one needs an infinite tesselation for it. Suppose we are given unit squares centered at points of integer lattice. Let the time to cross the square centered at (1,n) be 1/(|n|+1). Let the time to cross the square centerd at (0,n) or (2,n) be 1/100^(n+1). Then to go from (0,0) to (2,0) it is better to go far to cross the ridge at the low values of 1/(|n|+1). The further you go the better off you are. $\endgroup$
    – Yuri Bakhtin
    Commented Jun 7, 2011 at 16:37
1
$\begingroup$

Without loss of generality, let's assume the polygons are triangles; if not, you can covert them to triangles with e.g. ear-clipping.

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).

Some other references that might deal with the "exact" problem:

Fast exact and approximate geodesics on meshes. V. Surazhsky, T. Surazhsky, D. Kirsanov, S. Gortler, H. Hoppe. ACM Trans. on Graphics (SIGGRAPH), 24(3), 2005. http://research.microsoft.com/en-us/um/people/hoppe/geodesics.pdf

and

Theta*: Any-Angle Path Planning on Grids. K. Daniel, A. Nash, S. Koenig and A. Felner. Journal of Artificial Intelligence Research, 39, 533-579, 2010. http://idm-lab.org/project-o.html

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .