Approximate distance oracles for geometric graphs
Given a geometric t-spanner graph G in with n points and m edges, with edge lengths that lie within a polynomial (in n) factor of each other. Then, after O(m+nlogn) preprocessing, we present an approximation scheme to answer (1 + ϵ)-approximate shortest path queries in O(1) time. The data structure uses O(nlogn) space.
|Conference||13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002|
Gudmundsson, J. (Joachim), Levcopoulos, C. (Christos), Narasimhan, G. (Giri), & Smid, M. (2002). Approximate distance oracles for geometric graphs. Presented at the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002.