Approximation Algorithms for Shortest Descending Paths in Terrains

Mustaq Ahmed, Sandip Das, Sachin Lodha +3

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 f…