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

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