Let TeX be a collection of N pairwise vertex disjoint TeX -spanners where the weight of an edge is equal to the Euclidean distance between its endpoints. Let TeX be a graph on TeX with M edges of non-negative weight. The union of the two graphs is denoted TeX . We present a data structure of size TeX that answers (1+e)-approximate shortest path queries in TeX in constant time, where e>¿0 is constant.
|Title of host publication||Algorithms and Computation (Proceedings 15th International Symposium, ISAAC 2004, Hong Kong, December 20-22, 2004)|
|Editors||R. Fleischer, G. Trippen|
|Place of Publication||Berlin|
|Publication status||Published - 2004|
|Name||Lecture Notes in Computer Science|