Encoding Shortest Paths in Spatial Networks
A new data structure is presented which allows the search for shortest paths in spatially embedded planar networks in a worst-case time of O(k log n) (k and n being the number of nodes in the shortest path and in the network, respectively). This is an improvement over A* in large networks when k is not very small. The data structure requires O(n√n) space in the worst-case and is based on the idea to identify shortest path trees with the regions in the plane they cover. lt is further shown that an average searching time of O(k) can be expected for certain networks if estimates are stored additionally for these regions.
Nutzung und Vervielfältigung:
Alle Rechte vorbehalten