SHORTEST PATH QUERIES IN RECTILINEAR WORLDS
| Autor: | M.J. van Kreveld, M.T. de Berg, Mark H. Overmars, Bengt J. Nilsson |
|---|---|
| Rok vydání: | 1992 |
| Předmět: |
Discrete mathematics
Applied Mathematics Longest path problem Theoretical Computer Science Combinatorics Computational Mathematics Euclidean shortest path Computational Theory and Mathematics Shortest Path Faster Algorithm TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Shortest path problem Geometry and Topology K shortest path routing Yen's algorithm Distance Constrained Shortest Path First Mathematics |
| Zdroj: | International Journal of Computational Geometry & Applications. :287-309 |
| ISSN: | 1793-6357 0218-1959 |
| DOI: | 10.1142/s0218195992000172 |
| Popis: | 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( 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(nd log n) for d≥3, and in time O(n2) in the plane. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|