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

DOI10.1016/J.COMGEO.2022.101897MaRDI QIDQ2144452zbMATH OpenOpenAlexWikidataFDO

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

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

zbMATH Keywords

computational complexitylower boundweighted shortest path

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Polyhedral manifolds (52B70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

In the paper, the authors consider the \(d\)-dimensional weighted region shortest path problem. In this problem, we ask for finding the shortest path between two given points \(s\) and \(t\) in a \(d\)-dimensional polyhedral structure consisting of polyhedral cells having individual positive weights. They present lower bounds for the general \(d\)-dimensional case by constructing two novel \(d\)-dimensional polyhedral structures consisting of \(\mathcal{O}(n)\) convex cells in which a weighted shortest path has \(\Omega(n^d)\) cells crossings. The first polyhedral structure consists of a central cuboid and a set of satellite cuboids. The second structure consists of a central cuboid that is sliced, a set of shims (thin cuboids) and satellite cuboids.

Recommendations

• An \(\varOmega (n^3)\) lower bound on the number of cell crossings for weighted shortest paths in 3-dimensional polyhedral structures
• The weighted region problem
• SHORTEST RECTILINEAR PATHS AMONG WEIGHTED OBSTACLE
• Navigating Weighted Regions with Scattered Skinny Tetrahedra
• Navigating weighted regions with scattered skinny tetrahedra

Cites work

• A note on the unsolvability of the weighted region shortest path problem
• A note on two problems in connexion with graphs
• A survey of geodesic paths on 3D surfaces
• Algorithms for approximate shortest path queries on weighted polyhedral surfaces
• An \(\varOmega (n^3)\) lower bound on the number of cell crossings for weighted shortest paths in 3-dimensional polyhedral structures
• An approximation algorithm for computing shortest paths in weighted 3-d domains
• Determining approximate shortest paths on weighted polyhedral surfaces
• Geometry and light. The science of invisibility
• scientific article; zbMATH DE number 2107521 (Why is no real title available?)
• New results on shortest paths in three dimensions
• On finding approximate optimal paths in weighted regions
• TetGen, a Delaunay-based quality tetrahedral mesh generator
• The weighted region problem
• Triangulation refinement and approximate shortest paths in weighted regions

Cited in

(2)

• An \(\varOmega (n^3)\) lower bound on the number of cell crossings for weighted shortest paths in 3-dimensional polyhedral structures
• Path planning in a weighted planar subdivision under the Manhattan metric

Describes a project that uses

Uses Software

• Boost C++ Libraries
• ParaView
• Boost
• TetGen
• OpenVolumeMesh

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

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