Shortest descending paths through given faces (Q1025303)

The authors discuss minimal piecewise linear paths between two points on a polygonal terrain (height field) over the plane. Of primary interest is the shortest descending path; however, in this article they concentrate on enumerating the properties of the locally shortest descending path: the descending path that is minimal with respect to perturbations that preserve the endpoints. In particular, the authors show that in the case where a specific face sequence of the terrain is given, the locally shortest descending path is unique (and hence is the shortest descending path), and an approximation to it may be computed in time a fractional power of the number of faces. With the exception of the proofs of the last two properties, only elementary arguments are used, making the article accessible to a general audience.