Optimistic Shortest Paths on Uncertain Terrains

Shortest path problems are a well-studied class of problems in theoretical computer science. One particularly applicable type of shortest path problem is to find the geodesic shortest path on a terrain. This type of algorithm finds the shortest path between two points that stays on the surface of a terrain. The most popular methods for finding such a shortest path involve a variant of Dijkstra’s algorithm and run in time approximately !$#&% in the size of the terrain [5, 4]. These algorithms for calculating shortest paths on a terrain require a precise input; any errors in measuring the terrain translate into errors in the output of the algorithms. What appears to be a shortest path according to the given input may turn out to be longer than an alternate path in reality. Uncertain terrains are a new model for acknowledging and dealing with these errors. In this paper, we consider one version of the shortest path problem on uncertain terrains: the optimistic shortest path. Essentially, we would like to find the path whose length is smallest over all paths and over all possible real terrains. This seems to be a slight generalization of the traditional geodesic shortest path problem. We show that it is, in fact, more akin to the problem of finding the shortest path in three dimensions that avoids polyhedral obstacles. This problem was shown to be NP-hard by Canny and Reif [3] in 1986. It is from their proof that our work is derived.