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