Treffer: Shortest descending path

Finding the shortest path between two points in a terrain surface is a well-known problem. However, some special cases arise when we try to impose some conditions to this path: What happens when some parts of the terrain are worse to traverse than others (weighted terrains)? Or what happens when some direction in the terrain is much easier to travel (anisotropic paths)? In this paper we are going to focus our study in paths that can only be traversed in a horizontal or downward direction, or said otherwise, we forbid our path to increase its height while we are traversing it. These paths, also called shortest descending paths (SDP), have been studied in the past, and new algorithms have been devised in an effort to find them. However, no exact solutions have yet been found. We focus our efforts on collecting all the current information and algorithms, and try to improve any current result.