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.

Additional Metadata
Keywords Approximation algorithm, Computational geometry, Descending path, Gently descending path, Shortest path, Terrain
Persistent URL dx.doi.org/10.1016/j.jda.2009.05.001
Journal Journal of Discrete Algorithms
Ahmed, M. (Mustaq), Das, S. (Sandip), Lodha, S. (Sachin), Lubiw, A. (Anna), Maheshwari, A, & Roy, S. (Sasanka). (2010). Approximation algorithms for shortest descending paths in terrains. Journal of Discrete Algorithms, 8(2), 214–230. doi:10.1016/j.jda.2009.05.001