# Sequence of polygons containing the shortest path

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.

Mark

-

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

-
Thank you Joseph. You may be right, but I'm not sure I explained myself properly. I considered deriving the weight of each edge by multiplying the length of the edge by the lowest weight of the adjacent polygons, unless the edge is on the boundary, in which case there is only one polygon weight to choose. So, using your diagram and assuming that the squares are 6x6 units and the rectangles are 6x1 units, the blue line would have an overall cost of: 6x10 + 6x9 + 6x9 = 168 and the red line would cost: 6x10 + 1x11 + 6x1 + 1x11 + 6x9 = 142 Therefore the red line is chosen. –  Mark Freeman Jul 30 '11 at 14:37
Here is a link to a diagram showing what I mean. lh6.googleusercontent.com/-x6Ek83sHVLM/TjQWJ2Kqy6I/AAAAAAAAADI/… I would hope that the least cost path would pass through the lower weighted polygons on either side of this path, though not outside the polygons, i.e. regions 10, 11, 1, 11, 10, 9 Does that make sense? It might also be worth noting that the data I would be using is practically unbounded. –  Mark Freeman Jul 30 '11 at 14:53
@Mark: Indeed I misinterpreted your idea, thinking that "weight each edge based on the lower weight of its adjacent polygons" meant that the weight assigned to an edge is the lower weight of its adjacent polygons. I believe it still fails; I'll post an attempted counterexample. –  Joseph O'Rourke Jul 30 '11 at 18:10
@Joseph: I see, I naively disregarded the shape of the polygons, thinking I could somehow encode the cost of traversing their interior into their edges. I wonder if this is why much of the literature seems to be based on triangles, where the variability of shape is somehow minimised? Thank you again Joseph, I think I will now have to concentrate on approximate shortest paths and hope that I can find a method which does not require a data structure which is substantially larger than the original polygon edges. –  Mark Freeman Aug 2 '11 at 10:16