Approximate distance oracles for graphs with dense clusters

Let H-1 = (V,epsilon(1)) be a collection of N pairwise vertex disjoint O(1)-spanners where the weight of an edge is equal to the Euclidean distance between its endpoints. Let H-2 = (V, epsilon(2)) be the graph on V with M edges of non-negative weight. The union of the two graphs is denoted G = (V, epsilon(1) boolean OR epsilon(2)). We present a data structure of size O(M-2 + n log n) that answers (1 + epsilon)-approximate shortest path queries in G in constant time, where epsilon > 0 is constant. (C) 2006 Elsevier B.V. All tights reserved.