Back to search

University of British Columbia

Optimistic and pessimistic shortest paths on uncertain terrains

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2007

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Kholondyrev, Yury

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/32577

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Kholondyrev, Yury. Optimistic and pessimistic shortest paths on uncertain terrains. master's thesis, University of British Columbia, 2007. http://hdl.handle.net/2429/32577