Optimistic and pessimistic shortest paths on uncertain terrains
Yury Kholondyrev · cIRcle (University of British Columbia) · 2011
In the Uncertain Terrain Shortest Path problem we consider a triangulated terrain with vertices having uncertain Z-coordinates: each vertex is denned as a (x,y,z―,z+) tuple, where the z coordinate of a vertex is uncertain and can be anywhere in the range from z― to z+. We are looking for a path (defined by its projection to the XY- plane) such that, over all possible terrains, the path is as short as possible. We look at both pessimistic (terrain arranges itself to maximize the length of the path that we choose) and optimistic (terrain takes the state that minimizes the length of our path) scenarios. We restrict ourselves to walk only along the edges of the terrain. The unrestricted problem (when we are allowed to walk on the faces of the terrain) has been proven to be NP-hard in both pessimistic and optimistic scenarios. We prove that the edge-restricted pessimistic problem is NP-hard by providing a reduction from the SUBSET-SUM problem and give a polynomial time algorithm for the edge-restricted optimistic problem.