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

The d-dimensional weighted region shortest path problem asks for finding a shortest path between two given points s and t in a d-dimensional polyhedral structure consisting of polyhedral cells having individual positive weights. It is a generalization of the d-dimensional unweighted (Euclidean) shortest path problem for polyhedral structures. In the unweighted (Euclidean) setting, a shortest path visits, due to cell convexity, each polyhedral cell at most once. Surprisingly, this is no longer true for the weighted setting, which is a strong motivation for studying the complexity of weighted shortest paths in polyhedral structures. Previously, omega(n(2)), respectively omega(n(3)) lower bounds on the maximum number of cell crossings for weighted shortest paths in 2-dimensional, respectively 3-dimensional polyhedral structures have been obtained. In this paper, a new lower bound of omega(n(d)) is derived on the maximum number of cell crossings a weighted shortest path could take in d-dimensional polyhedral structures consisting of a linear number of O(n) polyhedral cells and cell faces. This new result is a generalization and sharpening of the formerly known lower bounds and has been a longstanding open problem for the general d-dimensional case. (C) 2022 Elsevier B.V. All rights reserved.