20080301
Approximate distance oracles for geometric spanners
Publication
Publication
ACM Transactions on Algorithms , Volume 4  Issue 1
Given an arbitrary real constant ε > 0, and a geometric graph G in ddimensional Euclidean space with n points, O(n) edges, and constant dilation, our main result is a data structure that answers (1 + ε)approximate shortestpathlength queries in constant time. The data structure can be constructed in O(n log n) time using O(n log n) space. This represents the first data structure that answers (1 + ε)approximate shortestpath queries in constant time, and hence functions as an approximate distance oracle. The data structure is also applied to several other problems. In particular, we also show that approximate shortestpath queries between vertices in a planar polygonal domain with rounded obstacles can be answered in constant time. Other applications include query versions of closestpair problems, and the efficient computation of the approximate dilations of geometric graphs. Finally, we show how to extend the main result to answer (1 + ε)approximate shortestpathlength queries in constant time for geometric spanner graphs with m = (n) edges. The resulting data structure can be constructed in O(m + n log n) time using O(n log n) space.
Additional Metadata  

, , , ,  
doi.org/10.1145/1328911.1328921  
ACM Transactions on Algorithms  
Organisation  Carleton University 
Gudmundsson, J. (Joachim), Levcopoulos, C. (Christos), Narasimhan, G. (Giri), & Smid, M. (2008). Approximate distance oracles for geometric spanners. ACM Transactions on Algorithms, 4(1). doi:10.1145/1328911.1328921
