Algorithms for approximate shortest path queries on weighted polyhedral surfaces

DOI10.1007/s00454-009-9204-0zbMath1207.68411OpenAlexW2074682596WikidataQ62037452 ScholiaQ62037452MaRDI QIDQ603866

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

Publication date: 8 November 2010

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

Full work available at URL: https://doi.org/10.1007/s00454-009-9204-0

zbMATH Keywords

shortest pathSteiner pointsseparatorapproximation graphquery algorithmweighted polyhedral surfaceweighted surface partioning

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items

Subdivision surface fitting to a dense mesh using ridges and umbilics, An \(\Omega (n^d)\) lower bound on the number of cell crossings for weighted shortest paths in \(d\)-dimensional polyhedral structures, An approximation algorithm for computing shortest paths in weighted 3-d domains, Approximating geodesic distances on 2-manifolds in image \(\mathbb R^3\), Fast query structures in anisotropic media, Path planning in a weighted planar subdivision under the Manhattan metric, Similarity of polygonal curves in the presence of outliers, A survey of geodesic paths on 3D surfaces, Approximating geodesic distances on 2-manifolds in \(\mathbb{R}^3\): The weighted case, Line facility location in weighted regions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate shortest paths and geodesic diameter on a convex polytope in three dimensions
• Partitioning planar graphs with vertex costs: Algorithms and applications
• Computing approximate shortest paths on convex polytopes
• Optimal shortest path queries in a simple polygon
• Metric entropy of some classes of sets with differentiable boundaries
• An optimal-time algorithm for shortest paths on a convex polytope in three dimensions
• The Discrete Geodesic Problem
• A separator theorem for graphs of bounded genus
• Partitioning planar graphs with costs and weights
• Determining approximate shortest paths on weighted polyhedral surfaces
• Querying approximate shortest paths in anisotropic regions
• Approximate Shortest Paths in Anisotropic Regions
• On Shortest Paths in Polyhedral Spaces
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• A Separator Theorem for Planar Graphs
• Constructing Approximate Shortest Path Maps in Three Dimensions
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• The weighted region problem
• Star Unfolding of a Polytope with Applications
• Approximating shortest paths on a convex polytope in three dimensions
• Planar spanners and approximate shortest path queries among obstacles in the plane
• ON GEOMETRIC PATH QUERY PROBLEMS
• Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus
• SHORTEST PATHS ON A POLYHEDRON, Part I: COMPUTING SHORTEST PATHS
• An ε — Approximation algorithm for weighted shortest paths on polyhedral surfaces
• On finding approximate optimal paths in weighted regions
• Sublinear Geometric Algorithms
• Additivity of the genus of a graph
• Approximate Shortest Path Queries on Weighted Polyhedral Surfaces
• Fundamentals of Computation Theory