This Issue


International Journal of Computational Geometry & Applications: Vol. 21, No. 04
Print ISSN: 0218-1959
Online ISSN: 1793-6357

 
writing-guides   ealerts
Connect with WS
 


SHORTEST DESCENDING PATHS: TOWARDS AN EXACT ALGORITHM

MUSTAQ AHMED

Google Inc., 1600 Amphitheatre Parkway, Mountain View, CA 94043, USA

ANNA LUBIW

David R. Cheriton School of Computer Science, University of Waterloo, 200 University Avenue West, ON N2L 3G1, Canada

Received: 27 March 2010
Revised: 24 September 2010

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.

Keywords: Continuous Dijkstra; sequence tree; Snell's law; terrain; computational geometry; optimization
Cited by (2):
, . (2014) Approximate Shortest Descending Paths. SIAM Journal on Computing 43:2, 410-428. Online publication date: 1-Jan-2014. [CrossRef]
. (2012) Near optimal algorithm for the shortest descending path on the surface of a convex terrain. Journal of Discrete Algorithms 15, 63-70. Online publication date: 1-Aug-2012. [CrossRef]