20110601
On the number of shortest descending paths on the surface of a convex terrain
Publication
Publication
Journal of Discrete Algorithms , Volume 9  Issue 2 p. 182 189
The shortest paths on the surface of a convex polyhedron can be grouped into equivalence classes according to the sequences of edges, consisting of ntriangular faces, that they cross. Mount (1990) [7] proved that the total number of such equivalence classes is Θ(n4). 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 zcoordinate 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 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 Π. We show that the number of equivalence classes of the shortest descending paths on the surface of a convex terrain is Θ(n4). We also discuss the difficulty of finding the number of equivalence classes on a convex polyhedron.
Additional Metadata  

Computational geometry, Shortest path, Terrain  
dx.doi.org/10.1016/j.jda.2010.12.002  
Journal of Discrete Algorithms  
Organisation  School of Computer Science 
Ahmed, M. (Mustaq), Maheshwari, A, Nandy, S.C. (Subhas C.), & Roy, S. (Sasanka). (2011). On the number of shortest descending paths on the surface of a convex terrain. Journal of Discrete Algorithms, 9(2), 182–189. doi:10.1016/j.jda.2010.12.002
