Approximate distance oracles for geometric graphs
Given a geometric t-spanner graph G in Ed with n points and m edges, with edge lengths that lie within a polynomial (in n) factor of each other. Then, after O(m+n log n) preprocessing, we present an approximation scheme to answer (1+ε)-approximate shortest path queries in O(1) time. The data structure uses O(n log n) space.
