Shortest monotone descent path problem in polyhedral terrain

DOI10.1016/J.COMGEO.2006.06.003MaRDI QIDQ876505zbMATH OpenOpenAlexFDO

Authors Sasanka Roy, Sandip Das, Subhas C. Nandy

Publication date 18 April 2007

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2006.06.003

zbMATH Keywords

complexitypolyhedral algorithm

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Numerical mathematical programming methods (65K05) Complexity and performance of numerical algorithms (65Y20)

Review text

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.

Recommendations

• STACS 2005
• Shortest descending paths through given faces
• An improved algorithm for the shortest descending path on a convex terrain
• Approximation algorithms for shortest descending paths in terrains
• Shortest Gently Descending Paths

Cites work

• A sweepline algorithm for Voronoi diagrams
• An efficient approximation algorithm for weighted region shortest path problem
• Approximating shortest paths on a nonconvex polyhedron
• Approximating shortest paths on weighted polyhedral surfaces
• Approximation algorithms for geometric shortest path problems
• Computational Science and Its Applications – ICCSA 2004
• Computing approximate shortest paths on convex polytopes
• Determining approximate shortest paths on weighted polyhedral surfaces
• Efficient computation of geodesic shortest paths
• Fundamentals of Computation Theory
• scientific article; zbMATH DE number 1391661 (Why is no real title available?)
• New results on shortest paths in three dimensions
• On Shortest Paths in Polyhedral Spaces
• Optimal Search in Planar Subdivisions
• Practical methods for approximating shortest paths on a convex polytope in \(\mathbb{R}^3\)
• SHORTEST PATHS ON A POLYHEDRON, Part I: COMPUTING SHORTEST PATHS
• The Discrete Geodesic Problem
• The weighted region problem
• Trekking in the alps without freezing or getting tired

Cited in

(9)

• Computing approximately shortest descending paths on convex terrains via multiple shooting
• Optimal facility location problem on polyhedral terrains using descending paths
• An improved algorithm for the shortest descending path on a convex terrain
• Shortest descending paths: towards an exact algorithm
• Shortest Gently Descending Paths
• Near optimal algorithm for the shortest descending path on the surface of a convex terrain
• On the number of shortest descending paths on the surface of a convex terrain
• STACS 2005
• Approximation algorithms for shortest descending paths in terrains

This page was built for publication: Shortest monotone descent path problem in polyhedral terrain

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q876505)