Article ID Journal Published Year Pages File Type
430622 Journal of Discrete Algorithms 2010 17 Pages PDF
Abstract

A path from s to t on a polyhedral terrain is descending if the height of a point p never increases while we move p along the path from s to t. No efficient algorithm is known to find a shortest descending path (SDP) from s to t in a polyhedral terrain. We present two approximation algorithms that solve the SDP problem on general terrains. We also introduce a generalization of the shortest descending path problem, called the shortest gently descending path (SGDP) problem, where a path descends, but not too steeply. The additional constraint to disallow a very steep descent makes the paths more realistic in practice. We present two approximation algorithms to solve the SGDP problem on general terrains. All of our algorithms are simple, robust and easy to implement.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , , , ,