Let G be a geometric t-spanner in Ed with n vertices and m edges, where t is a constant. We show that G can be preprocessed in O(m log n) time, such that (1 + ε)-approximate shortest-path queries in G can be answered in O(1) time. The data structure uses O(nlogn) space.

Additional Metadata
Persistent URL dx.doi.org/10.1007/3-540-36136-7_32
Citation
Gudmundsson, J. (Joachim), Levcopoulos, C. (Christos), Narasimhan, G. (Giri), & Smid, M. (2002). Approximate distance oracles revisited. doi:10.1007/3-540-36136-7_32