Shortest Descending Paths through Given 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. No efficient algorithm is known to find a shortest descending path from s to t in a polyhedral terrain. We give some properties of such paths. In the case where the face sequence is specified, we show that the shortest descending path is unique, and give an ɛ-approximation algorithm that computes)) time. the path in O(n 3.5 log ( 1 ɛ