Near optimal algorithm for the shortest descending path on the surface of a convex terrain

We study the problem of finding a shortest descending path (SDP) between a pair of points, called source (s) and destination (t), on the surface of a triangulated convex terrain with n faces. 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  . Time and space complexity requirement of our algorithm are O(μ(n)logn) and O(τ(n))O(τ(n)), respectively. Here μ(n)μ(n) and τ(n)τ(n) are time and space complexity requirement for finding shortest geodesic path (SGP) between a pair of points on the surface of a convex polyhedra. The best known bounds on μ(n)μ(n) and τ(n)τ(n) are both O(nlogn) due to Schreiber and Sharir (2008) [11]. Earlier best known time and space complexity results of SDP on convex terrain were O(n2logn) and O(n2)O(n2), respectively, and appears in Roy et al. (2007) [10]. Thus our algorithm improves both time and space complexity requirement of SDP problem by almost a linear factor over earlier best known results.