Shortest descending paths through given faces (Q1025303)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Shortest descending paths through given faces |
scientific article |
Statements
Shortest descending paths through given faces (English)
0 references
18 June 2009
0 references
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.
0 references
shortest descending paths
0 references
shortest paths
0 references
terrain
0 references
convex optimization
0 references