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:
- I use the edges of the polygons as a graph
- weight each edge based on the lower weight of its adjacent polygons
- use Dijkstra’s algorithm to find the shortest path along the edges between nodes s and t
- 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: http://mathoverflow.net/questions/66990/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,