On the number of shortest descending paths on the surface of a convex terrain

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) [7] proved that the total number of such equivalence classes is circle minus(n(4)). 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 Pi such that for every pair of points p = (x(p), y(p), z(p)) and q = (x(q), y(q), z(q)) on., if dist(s, p) < dist(s, q) then z(p)>= z(q). Here dist(s, p) denotes the distance of p from s along Pi.We show that the number of equivalence classes of the shortest descending paths on the surface of a convex terrain is circle minus(n(4)). We also discuss the difficulty of finding the number of equivalence classes on a convex polyhedron. (C) 2010 Elsevier B.V. All rights reserved.