Shortest paths on uncertain terrains
Chris Gray · cIRcle (University of British Columbia) · 2009
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).