Near optimal algorithm for the shortest descending path on the surface of a convex terrain

DOI10.1016/J.JDA.2012.03.001MaRDI QIDQ450580zbMATH OpenOpenAlexFDO

Authors Sasanka Roy

Publication date 13 September 2012

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2012.03.001

zbMATH Keywords

computational geometrygeodesic pathshortest pathterrain

Mathematics Subject Classification ID

Convex sets in (3) dimensions (including convex surfaces) (52A15) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Recommendations

• Approximate shortest descending paths
• Approximation algorithms for shortest descending paths in terrains
• Shortest descending paths: towards an exact algorithm
• Approximate shortest descending paths
• An improved algorithm for the shortest descending path on a convex terrain

Cites work

• An optimal-time algorithm for shortest paths on a convex polytope in three dimensions
• Approximation algorithms for shortest descending paths in terrains
• On Shortest Paths in Polyhedral Spaces
• On the number of shortest descending paths on the surface of a convex terrain
• Shortest descending paths through given faces
• Shortest descending paths: towards an exact algorithm
• Shortest monotone descent path problem in polyhedral terrain
• SHORTEST PATHS ON A POLYHEDRON, Part I: COMPUTING SHORTEST PATHS
• The Discrete Geodesic Problem
• The Number of Shortest Paths on the Surface of a Polyhedron
• Trekking in the alps without freezing or getting tired

Cited in

(7)

• 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
• Approximate shortest descending paths
• On the number of shortest descending paths on the surface of a convex terrain
• Approximate shortest descending paths

This page was built for publication: Near optimal algorithm for the shortest descending path on the surface of a convex terrain

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