Approximate shortest descent path on a terrain
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.
|19th Annual Canadian Conference on Computational Geometry, CCCG 2007|
|Organisation||Computational Geometry Lab|
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.