An approximation algorithm for computing shortest paths in weighted 3-d domains

DOI10.1007/s00454-013-9486-0zbMath1284.68652OpenAlexW1798872925WikidataQ62037428 ScholiaQ62037428MaRDI QIDQ2391841

Hristo N. Djidjev, Jörg-Rüdiger Sack, Anil Maheshwari, Lyudmil Aleksandrov

Publication date: 5 August 2013

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-013-9486-0

zbMATH Keywords

approximation algorithmsVoronoi diagramsshortest path problemsweighted pathsweighted 3-d domains

Mathematics Subject Classification ID

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

Related Items (3)

An \(\Omega (n^d)\) lower bound on the number of cell crossings for weighted shortest paths in \(d\)-dimensional polyhedral structures ⋮ Navigating Weighted Regions with Scattered Skinny Tetrahedra ⋮ Path planning in a weighted planar subdivision under the Manhattan metric

Uses Software

• BUSHWHACK

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for approximate shortest path queries on weighted polyhedral surfaces
• Abstract Voronoi diagrams revisited
• An algorithm for shortest-path motion in three dimensions
• The algebraic degree of geometric optimization problems
• Concrete and abstract Voronoi diagrams
• Pseudo approximation algorithms with applications to optimal motion planning
• Abstract Voronoi diagram in 3-space
• Movement planning in the presence of flows
• Approximation algorithms for geometric shortest path problems
• Determining approximate shortest paths on weighted polyhedral surfaces
• Constructing Approximate Shortest Path Maps in Three Dimensions
• The weighted region problem
• Approximate Euclidean Shortest Paths in 3-Space
• Precision-Sensitive Euclidean Shortest Path in 3-Space
• New results on shortest paths in three dimensions
• On finding approximate optimal paths in weighted regions
• Approximating shortest paths on weighted polyhedral surfaces

This page was built for publication: An approximation algorithm for computing shortest paths in weighted 3-d domains