UBC Theses and Dissertations
Shortest paths on uncertain terrains Gray, Chris
In this dissertation, we introduce the concept of uncertain terrains first suggested by Jorg Sack. We then examine the problem of finding the shortest path that stays on these terrains given certain assumptions about the terrains. We show that this problem is NP-hard under two fairly natural assumptions (meaning that we do not expect any polynomial time algorithm that finds these paths to be discovered).
Item Citations and Data