Approximate distance oracles for geometric graphs
Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan, Michiel Smid · 2002
Given a geometric t-spanner graph G in E d 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.