An \(\Omega (n^d)\) lower bound on the number of cell crossings for weighted shortest paths in \(d\)-dimensional polyhedral structures
DOI10.1016/j.comgeo.2022.101897zbMath1502.68300OpenAlexW4280652037WikidataQ114195503 ScholiaQ114195503MaRDI QIDQ2144452
Anil Maheshwari, Jörg-Rüdiger Sack, Frank Bauernöppel
Publication date: 13 June 2022
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.comgeo.2022.101897
Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Polyhedral manifolds (52B70)
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- Algorithms for approximate shortest path queries on weighted polyhedral surfaces
- A survey of geodesic paths on 3D surfaces
- An \(\varOmega (n^3)\) lower bound on the number of cell crossings for weighted shortest paths in 3-dimensional polyhedral structures
- A note on the unsolvability of the weighted region shortest path problem
- An approximation algorithm for computing shortest paths in weighted 3-d domains
- Determining approximate shortest paths on weighted polyhedral surfaces
- The weighted region problem
- TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator
- New results on shortest paths in three dimensions
- Triangulation Refinement and Approximate Shortest Paths in Weighted Regions
- On finding approximate optimal paths in weighted regions
This page was built for publication: An \(\Omega (n^d)\) lower bound on the number of cell crossings for weighted shortest paths in \(d\)-dimensional polyhedral structures
