Back to Search
Start Over
Shortest Monotone Descent Path Problem in Polyhedral Terrain.
- Source :
- STACS 2005; 2005, p281-292, 12p
- Publication Year :
- 2005
-
Abstract
- Given a polyhedral terrain with n vertices, the shortest monotone descent path problem deals with finding the shortest path between a pair of points, called source (s) and destination (t) such that the path is constrained to lie on the surface of the terrain, and for every pair of points p = (x(p), y(p), z(p)) and q = (x(q), y(q), z(q)) on the path, if dist(s,p) < dist(s,q) then z(p) > z(q), where dist(s,p) denotes the distance of p from s along the aforesaid path. This is posed as an open problem in [3]. We show that for some restricted classes of polyhedral terrain, the optimal path can be identified in polynomial time. We also propose an elegant method which can return near-optimal path for the general terrain in polynomial time. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783540249986
- Database :
- Supplemental Index
- Journal :
- STACS 2005
- Publication Type :
- Book
- Accession number :
- 32980614