An \(\varOmega (n^3)\) lower bound on the number of cell crossings for weighted shortest paths in 3-dimensional polyhedral structures

DOI10.1007/978-3-030-61792-9_19zbMath1502.68301OpenAlexW3106756511MaRDI QIDQ2081620

Anil Maheshwari, Frank Bauernöppel, Jörg-Rüdiger Sack

Publication date: 13 October 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-61792-9_19

zbMATH Keywords

computational complexitylower boundcomputational geometryweighted shortest path

Mathematics Subject Classification ID

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)

An \(\Omega (n^d)\) lower bound on the number of cell crossings for weighted shortest paths in \(d\)-dimensional polyhedral structures

This page was built for publication: An \(\varOmega (n^3)\) lower bound on the number of cell crossings for weighted shortest paths in 3-dimensional polyhedral structures