A path froms 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. We 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. e give two approximation algorithms (more precisely, FPTASs) to solve the SGDP problem on general terrains.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-642-00202-1_6
Citation
Ahmed, M. (Mustaq), Lubiw, A. (Anna), & Maheshwari, A. (2009). Shortest gently descending paths. doi:10.1007/978-3-642-00202-1_6