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

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.