Shortest monotone descent path problem in polyhedral terrain (Q876505)

Given a polyhedral terrain with \(n\) vertices, authors deal with the shortest monotone descent path problem. This problem consists in finding the shortest path between a pair of points, called source (s) and destination (t) such that the path is constrained to lie on the surface of the terrain, and for every pair of points \(p=(x(p),y(p),z(p)),\, q=(x(q),y(q),z(q))\) on the path, if \(dist(s,p)<dist(s,q)\) then \(z(p)\geq z(q)\), where \(dist(s,p)\) denotes the distance of \(p\) from \(s\) along the aforesaid path. The authors show that for some classes of polyhedral terrains, that the optimal path can be identified in polynomial time. For the general terrain the problem is still unsolved.