Shortest path queries in rectilinear worlds of higher dimension (extended abstract)
Mark de Berg, Marc J. van Kreveld, Bengt J. Nilsson · 1991
In this paper, a data structure is given for higher dimensional shortest path queries.For a set of n axisparallel boxes in d-space and a fixed target, it is possible with this sttucturc to find a shortest rectilinear path from any point in d-space to this target, where the path does not cross any box.Alternatively, it is possible to find the length of the path.The metric considered is a generalization of the L1 -metric and the link metric, where the length of a path is its L1-length plus some (fixed) constant times the number of turns on the path.The data structure uses O ((n log n)d-l ) space to store, and a query takes O (logd-1 n) time (plus the output size if the path must be reported).As a byproduct a solution to the single shot problem is obtained; the shortest path between two given points can be computed in time O (nd log n).