Approximation algorithms for shortest descending paths in terrains

DOI10.1016/J.JDA.2009.05.001MaRDI QIDQ972363zbMATH OpenOpenAlexFDO

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

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

approximation algorithmcomputational geometryshortest pathterraindescending pathgently descending path

Mathematics Subject Classification ID

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

Recommendations

• Shortest Gently Descending Paths
• Approximate shortest descending paths
• Approximate shortest descending paths
• Shortest descending paths through given faces
• Shortest descending paths: towards an exact algorithm

Cites work

• scientific article; zbMATH DE number 5506188 (Why is no real title available?)
• scientific article; zbMATH DE number 5506207 (Why is no real title available?)
• scientific article; zbMATH DE number 2080988 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• An algorithm for shortest-path motion in three dimensions
• An ε — Approximation algorithm for weighted shortest paths on polyhedral surfaces
• Approximate shortest paths in anisotropic regions
• Approximation algorithms for geometric shortest path problems
• Computing approximate shortest paths on convex polytopes
• Constructing Approximate Shortest Path Maps in Three Dimensions
• Determining approximate shortest paths on weighted polyhedral surfaces
• Fibonacci heaps and their uses in improved network optimization algorithms
• On discretization methods for approximating optimal paths in regions with direction-dependent costs
• On finding approximate optimal paths in weighted regions
• SHORTEST PATHS ON A POLYHEDRON, Part I: COMPUTING SHORTEST PATHS
• Shortest Gently Descending Paths
• Shortest descending paths through given faces
• Shortest descending paths: towards an exact algorithm
• Shortest monotone descent path problem in polyhedral terrain
• Shortest paths on realistic polyhedra
• The Discrete Geodesic Problem
• The weighted region problem
• Trekking in the alps without freezing or getting tired

Cited in

(12)

• Optimal facility location problem on polyhedral terrains using descending paths
• Approximate shortest descending paths
• scientific article; zbMATH DE number 7151640 (Why is no real title available?)
• 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
• Linear Search with Terrain-Dependent Speeds
• Shortest Gently Descending Paths
• Approximate shortest descending paths
• Navigating weighted regions with scattered skinny tetrahedra
• Shortest descending paths: towards an exact algorithm
• Computing approximately shortest descending paths on convex terrains via multiple shooting

Describes a project that uses

Uses Software

• BUSHWHACK

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

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