TY - JOUR

T1 - Shortest path queries in rectilinear worlds

AU - Berg, de, M.

AU - Kreveld, van, M.J.

AU - Nilsson, B.J.

AU - Overmars, M.H.

PY - 1992

Y1 - 1992

N2 - In this paper, a data structure is given for two and higher dimensional shortest path queries. For a set of n axis-parallel rectangles in the plane, or boxes in d-space, and a fixed target, it is possible with this structure to find a shortest rectilinear path avoiding all rectangles or boxes from any point to this target. 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 has size O((n log n)d-1), and a query takes O(logd-1 n) time (plus the output size if the path must be reported). As a byproduct, a relatively simple solution to the single shot problem is obtained; the shortest path between two given points can be computed in time O(nd log n) for d=3, and in time O(n2) in the plane.

AB - In this paper, a data structure is given for two and higher dimensional shortest path queries. For a set of n axis-parallel rectangles in the plane, or boxes in d-space, and a fixed target, it is possible with this structure to find a shortest rectilinear path avoiding all rectangles or boxes from any point to this target. 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 has size O((n log n)d-1), and a query takes O(logd-1 n) time (plus the output size if the path must be reported). As a byproduct, a relatively simple solution to the single shot problem is obtained; the shortest path between two given points can be computed in time O(nd log n) for d=3, and in time O(n2) in the plane.

U2 - 10.1142/S0218195992000172

DO - 10.1142/S0218195992000172

M3 - Article

SN - 0218-1959

VL - 2

SP - 287

EP - 309

JO - International Journal of Computational Geometry and Applications

JF - International Journal of Computational Geometry and Applications

IS - 3

ER -