| Approximation Algorithms for Shortest Descending Paths in Terrains (2008) | |||||||||
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 give two approximation algorithms (more precisely, FPTASs) that solve the SDP problem on general terrains. Both algorithms are simple, robust and easy to implement.. Comment: 24 pages, 8 figures | |||||||||
Publication details | |||||||||
| |||||||||