An approximation algorithm for computing shortest paths in weighted 3-d domains
From MaRDI portal
Publication:2391841
DOI10.1007/s00454-013-9486-0zbMath1284.68652WikidataQ62037428 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
approximation algorithms; Voronoi diagrams; shortest path problems; weighted paths; weighted 3-d domains
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
68W25: Approximation algorithms
Related Items
Navigating Weighted Regions with Scattered Skinny Tetrahedra, Path planning in a weighted planar subdivision under the Manhattan metric, An \(\Omega (n^d)\) lower bound on the number of cell crossings for weighted shortest paths in \(d\)-dimensional polyhedral structures
Uses Software
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