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

DOI10.1016/j.jda.2012.03.001zbMath1255.68197OpenAlexW2093057316MaRDI QIDQ450580

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

shortest pathcomputational geometrygeodesic pathterrain

Mathematics Subject Classification ID

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

Related Items (3)

An improved algorithm for the shortest descending path on a convex terrain ⋮ Optimal facility location problem on polyhedral terrains using descending paths ⋮ Computing approximately shortest descending paths on convex terrains via multiple shooting

Cites Work

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

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