Approximation algorithms for shortest descending paths in terrains

DOI10.1016/j.jda.2009.05.001zbMath1190.90252OpenAlexW2127945324MaRDI QIDQ972363

Sasanka Roy, Anil Maheshwari, Sandip Das, Anna Lubiw, Sachin Lodha, Mustaq Ahmed

Publication date: 25 May 2010

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

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

zbMATH Keywords

shortest pathapproximation algorithmcomputational geometryterraindescending pathgently descending path

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (8)

SHORTEST DESCENDING PATHS: TOWARDS AN EXACT ALGORITHM ⋮ Unnamed Item ⋮ Navigating Weighted Regions with Scattered Skinny Tetrahedra ⋮ Optimal facility location problem on polyhedral terrains using descending paths ⋮ Near optimal algorithm for the shortest descending path on the surface of a convex terrain ⋮ Computing approximately shortest descending paths on convex terrains via multiple shooting ⋮ On the number of shortest descending paths on the surface of a convex terrain ⋮ Shortest Gently Descending Paths

Uses Software

• BUSHWHACK

Cites Work

• Shortest monotone descent path problem in polyhedral terrain
• Shortest descending paths through given faces
• On discretization methods for approximating optimal paths in regions with direction-dependent costs
• An algorithm for shortest-path motion in three dimensions
• Trekking in the alps without freezing or getting tired
• SHORTEST DESCENDING PATHS: TOWARDS AN EXACT ALGORITHM
• The Discrete Geodesic Problem
• Approximation algorithms for geometric shortest path problems
• Determining approximate shortest paths on weighted polyhedral surfaces
• Shortest paths on realistic polyhedra
• Shortest Gently Descending Paths
• Constructing Approximate Shortest Path Maps in Three Dimensions
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• The weighted region problem
• SHORTEST PATHS ON A POLYHEDRON, Part I: COMPUTING SHORTEST PATHS
• An ε — Approximation algorithm for weighted shortest paths on polyhedral surfaces
• Fibonacci heaps and their uses in improved network optimization algorithms
• Computing approximate shortest paths on convex polytopes
• On finding approximate optimal paths in weighted regions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximation algorithms for shortest descending paths in terrains