Back to Search
Start Over
On the number of shortest descending paths on the surface of a convex terrain.
- Source :
- Journal of Discrete Algorithms; Jun2011, Vol. 9 Issue 2, p182-189, 8p
- Publication Year :
- 2011
-
Abstract
- Abstract: The shortest paths on the surface of a convex polyhedron can be grouped into equivalence classes according to the sequences of edges, consisting of n-triangular faces, that they cross. Mount (1990) proved that the total number of such equivalence classes is . In this paper, we consider descending paths on the surface of a 3D terrain. A path in a terrain is called a descending path if the z-coordinate of a point p never increases, if we move p along the path from the source to the target. More precisely, a descending path from a point s to another point t is a path Π such that for every pair of points and on Π, if then . Here denotes the distance of p from s along Π. We show that the number of equivalence classes of the shortest descending paths on the surface of a convex terrain is . We also discuss the difficulty of finding the number of equivalence classes on a convex polyhedron. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 15708667
- Volume :
- 9
- Issue :
- 2
- Database :
- Supplemental Index
- Journal :
- Journal of Discrete Algorithms
- Publication Type :
- Academic Journal
- Accession number :
- 59172387
- Full Text :
- https://doi.org/10.1016/j.jda.2010.12.002