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

DOI10.1007/S00454-013-9486-0MaRDI QIDQ2391841zbMATH OpenOpenAlexDBLPWikidataFDO

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

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)

Recommendations

• Approximation algorithms for geometric shortest path problems
• Navigating weighted regions with scattered skinny tetrahedra
• Navigating Weighted Regions with Scattered Skinny Tetrahedra
• Computational Science and Its Applications – ICCSA 2004
• Approximating shortest paths on weighted polyhedral surfaces

Cites work

• scientific article; zbMATH DE number 554764 (Why is no real title available?)
• scientific article; zbMATH DE number 2080988 (Why is no real title available?)
• scientific article; zbMATH DE number 1424293 (Why is no real title available?)
• Abstract Voronoi diagram in 3-space
• Abstract Voronoi diagrams revisited
• Algorithms for approximate shortest path queries on weighted polyhedral surfaces
• An algorithm for shortest-path motion in three dimensions
• Approximate Euclidean Shortest Paths in 3-Space
• Approximate Euclidean shortest paths amid convex obstacles
• Approximating shortest paths on weighted polyhedral surfaces
• Approximation algorithms for geometric shortest path problems
• Concrete and abstract Voronoi diagrams
• Constructing Approximate Shortest Path Maps in Three Dimensions
• Determining approximate shortest paths on weighted polyhedral surfaces
• Movement planning in the presence of flows
• New results on shortest paths in three dimensions
• On finding approximate optimal paths in weighted regions
• Precision-Sensitive Euclidean Shortest Path in 3-Space
• Pseudo approximation algorithms with applications to optimal motion planning
• The algebraic degree of geometric optimization problems
• The weighted region problem

Cited in

(6)

• Constructing Approximate Shortest Path Maps in Three Dimensions
• APPROXIMATE SHORTEST HOMOTOPIC PATHS IN WEIGHTED REGIONS
• An \(\Omega (n^d)\) lower bound on the number of cell crossings for weighted shortest paths in \(d\)-dimensional polyhedral structures
• Path planning in a weighted planar subdivision under the Manhattan metric
• An \(\varOmega (n^3)\) lower bound on the number of cell crossings for weighted shortest paths in 3-dimensional polyhedral structures
• Navigating weighted regions with scattered skinny tetrahedra

Describes a project that uses

Uses Software

• BUSHWHACK

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

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