Approximate distance oracles for graphs with dense clusters (Q883232)

Let \(H_1=(V,E_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,E_2)\) be the graph on \(V\) with \(M\) edges of non-negative weight. The union of the two graphs is denoted \(G=(V,E_1\cup E_2)\). The authors present a data structure of size \(O(M^2+n\log n)\) that answers \((1+\varepsilon)\)-approximate shortest path queries in \(G\) in constant time, where \(\varepsilon>0\) is constant.