Portal de Periódicos da CAPES

SHORTEST PATH QUERIES IN RECTILINEAR WORLDS

1992; World Scientific; Volume: 02; Issue: 03 Linguagem: Inglês

10.1142/s0218195992000172

1793-6357

Mark de Berg, Marc van Kreveld, Bengt J. Nilsson, Mark Overmars,

Algorithms and Data Compression

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 L 1 -metric and the link metric, where the length of a path is its L 1 -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( log d−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(n d log n) for d≥3, and in time O(n 2 ) in the plane.