Encoding Shortest Paths in Spatial Networks

Erwig, Martin GND

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.

Vorschau

Zitieren

Zitierform:

Erwig, Martin: Encoding Shortest Paths in Spatial Networks. Hagen 1991. FernUniversität in Hagen.

Zugriffsstatistik

Gesamt

Volltextzugriffe:
Metadatenansicht:

12 Monate

Volltextzugriffe:
Metadatenansicht:

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export

powered by MyCoRe