Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1142/S0218195992000172 | INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS |
Keywords | DocType | Volume |
Shortest paths, rectilinear paths, rectilinear obstacles, combined metric | Journal | 2 |
Issue | ISSN | Citations |
3 | 0218-1959 | 15 |
PageRank | References | Authors |
0.82 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark De Berg | 1 | 1497 | 153.24 |
| Marc J. van Kreveld | 2 | 1702 | 166.91 |
| Bengt J. Nilsson | 3 | 210 | 24.43 |
| Mark H. Overmars | 4 | 4572 | 518.80 |