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
    0 references
    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
    0 references
    shortest descending paths
    0 references
    shortest paths
    0 references
    terrain
    0 references
    convex optimization
    0 references

    Identifiers