SHORTEST DESCENDING PATHS: TOWARDS AN EXACT ALGORITHM
Google Inc., 1600 Amphitheatre Parkway, Mountain View, CA 94043, USA
David R. Cheriton School of Computer Science, University of Waterloo, 200 University Avenue West, ON N2L 3G1, Canada
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. Although a shortest path on a terrain unfolds to a straight line, a shortest descending path (SDP) does not. We give a full characterization of the bend angles of an SDP, showing that they follow a generalized form of Snell's law of refraction of light. The complexity of finding SDPs is open—only approximation algorithms are known. We reduce the SDP problem to the problem of finding an SDP through a given sequence of faces. We give polynomial time algorithms for SDPs on two special classes of terrains, but argue that the general case will be difficult.



