A path from a point s to a point t on the surface of a polyhedral terrain is said to be descent if 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. Although an efficient algorithm to decide if there is a descending path between two points is known for more than a decade, no efficient algorithm is yet known to find a shortest descending path from s to t in a polyhedral terrain. In this paper we propose an (1 + ε-approximation algorithm running in polynomial time for the same.

Additional Metadata
Conference 19th Annual Canadian Conference on Computational Geometry, CCCG 2007
Citation
Roy, S. (Sasanka), Lodha, S. (Sachin), Dast, S. (Sandip), & Maheshwari, A. (2007). Approximate shortest descent path on a terrain. Presented at the 19th Annual Canadian Conference on Computational Geometry, CCCG 2007.