Approximate distance oracles for geometric spanners
(2008) In ACM Transactions on Algorithms 4(1). Abstract
 Given an arbitrary real constant epsilon > 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 + epsilon)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 + epsilon)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... (More)
 Given an arbitrary real constant epsilon > 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 + epsilon)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 + epsilon)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 + epsilon)approximate shortestpathlength queries in constant time for geometric spanner graphs with m = omega(n) edges. The resulting data structure can be constructed in O(m + n log n) time using O(n log n) space. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/1428219
 author
 Gudmundsson, Joachim; Levcopoulos, Christos ^{LU} ; Narasimhan, Giri and Smid, Michiel
 organization
 publishing date
 2008
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 geometric graphs, approximation algorithm, Shortest paths, computational geometry, spanners
 in
 ACM Transactions on Algorithms
 volume
 4
 issue
 1
 publisher
 ACM
 external identifiers

 wos:000265816600010
 scopus:42149179298
 ISSN
 15496333
 DOI
 10.1145/1328911.1328921
 project
 VR 20054085
 language
 English
 LU publication?
 yes
 id
 acd2dec51ee244fabc99bab2723cb712 (old id 1428219)
 date added to LUP
 20090625 10:37:05
 date last changed
 20170101 04:33:55
@article{acd2dec51ee244fabc99bab2723cb712, abstract = {Given an arbitrary real constant epsilon > 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 + epsilon)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 + epsilon)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 + epsilon)approximate shortestpathlength queries in constant time for geometric spanner graphs with m = omega(n) edges. The resulting data structure can be constructed in O(m + n log n) time using O(n log n) space.}, author = {Gudmundsson, Joachim and Levcopoulos, Christos and Narasimhan, Giri and Smid, Michiel}, issn = {15496333}, keyword = {geometric graphs,approximation algorithm,Shortest paths,computational geometry,spanners}, language = {eng}, number = {1}, publisher = {ACM}, series = {ACM Transactions on Algorithms}, title = {Approximate distance oracles for geometric spanners}, url = {http://dx.doi.org/10.1145/1328911.1328921}, volume = {4}, year = {2008}, }