An ε — Approximation algorithm for weighted shortest paths on polyhedral surfaces

DOI10.1007/BFb0054351zbMath1504.68243OpenAlexW111486705WikidataQ62037490 ScholiaQ62037490MaRDI QIDQ5054837

Jörg-Rüdiger Sack, Anil Maheshwari, M. Lanthier, Lyudmil Aleksandrov

Publication date: 9 December 2022

Published in: Algorithm Theory — SWAT'98 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bfb0054351

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items

Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces, An ε — Approximation algorithm for weighted shortest paths on polyhedral surfaces, On approximating shortest paths in weighted triangular tessellations, Algorithms for approximate shortest path queries on weighted polyhedral surfaces, Path planning in a weighted planar subdivision under the Manhattan metric, Approximate Shortest Paths in Polygons with Violations, On representing a simple polygon perceivable to a blind person, An Experimental Study of Weighted k-Link Shortest Path Algorithms, An optimal-time algorithm for shortest paths on a convex polytope in three dimensions, Approximation algorithms for shortest descending paths in terrains, On approximating shortest paths in weighted triangular tessellations, Pursuit evasion on polyhedral surfaces, Modeling Optimal Beam Treatment with Weighted Regions for Bio-medical Applications, On discretization methods for approximating optimal paths in regions with direction-dependent costs

Cites Work

• Unnamed Item
• An algorithm for shortest-path motion in three dimensions
• How to take short cuts
• On Shortest Paths in Polyhedral Spaces
• The weighted region problem
• An ε — Approximation algorithm for weighted shortest paths on polyhedral surfaces
• Fibonacci heaps and their uses in improved network optimization algorithms