Sequence of polygons containing the shortest path

Question

Hello all,

I’m looking at the weighted region problem i.e. trying to find the shortest weighted path across a polygon subdivision, but at this point in my work, I only need to know the sequence of polygons through which the shortest path will pass.

I have an idea but I’m having trouble finding the mathematical justification for it, so I wonder if someone can either confirm my thoughts (or point me in the right direction)?

This is the idea:

1. I use the edges of the polygons as a graph
2. weight each edge based on the lower weight of its adjacent polygons
3. use Dijkstra’s algorithm to find the shortest path along the edges between nodes s and t
4. select the lower weight polygons from either side of this path.

Would this algorithm work, including when the polygons are non-convex?

I have read the paper by Mitchell and Papadimitriou, mentioned in the question: Shortest Path in Plane, along with several others, but the closest reference to my problem I can find is in ‘Fast Exact and Approximate Geodesics on Meshes’ by Vitaly Surazhsky et al which states in section 5:

“Using Dijkstra search on edges only, compute an upper bound distance Ust(Dijkstra) by searching from vs until vt is reached.”

The paper however is assuming that the division is a triangular mesh and I don’t know if this statement can be generalised to a set of non-convex polygons.

My background is in geography and physics (very rusty now though) so I’m ok with maths to a point, but I’ve never developed a proof. Also, I am looking at this problem from a practical point of view, in that I would like to find a solution which will work with large quantities of data in a “reasonable”, time, even if the solution is approximate.

Thank you for any help you can give,

Mark

Answer 1

[My first counterexample was based on a misinterpretation of the edge weights; now removed as irrelevant (but this explains the comments below). Counterexample to a correct interpretation follows.]

---

Added. (30Jul11). Sorry for misinterpreting. I now see that the weight of each edge in your graph is the Euclidean length of the edge times the lower weight of the region to either side. Here is an example where I believe the algorithm fails, where I use $w$ for weight and $l$ for length.
          
Your algorithm would select the purple path, because its cost is $0+\frac{3}{2}+0$, whereas the red path has cost about $0+\frac{\pi}{2}+0 > \frac{3}{2}$, and so is rejected by the algorithm. (Of course I could make the red cost approach $\frac{\pi}{2}$ by increasing the number of edges in the regular polygon; the zero weights could be $\epsilon$-weights if you want them all to be positive). I am assuming surrounding regions that lead to the weights shown being the only relevant ones. So the algorithm thinks passing through the mauve rectangle is best. But the green path (not visible to your algorithm because it does not follow edges of regions) has cost $0+1+0$. The problem is that following the edges of a convex region overestimates the cost of traversing through the interior of that region, and this overestimate could lead to the algorithm choosing a nonoptimal route.