Advanced

Approximate distance oracles for geometric spanners

Gudmundsson, Joachim; Levcopoulos, Christos LU ; Narasimhan, Giri and Smid, Michiel (2008) In ACM Transactions on Algorithms 4(1).
Abstract
Given an arbitrary real constant epsilon > 0, and a geometric graph G in d-dimensional Euclidean space with n points, O(n) edges, and constant dilation, our main result is a data structure that answers (1 + epsilon)-approximate shortest-path-length 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 shortest-path 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 shortest-path 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 d-dimensional Euclidean space with n points, O(n) edges, and constant dilation, our main result is a data structure that answers (1 + epsilon)-approximate shortest-path-length 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 shortest-path 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 shortest-path queries between vertices in a planar polygonal domain with "rounded" obstacles can be answered in constant time. Other applications include query versions of closest-pair 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 shortest-path-length 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:
author
organization
publishing date
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
1549-6333
DOI
10.1145/1328911.1328921
project
VR 2005-4085
language
English
LU publication?
yes
id
acd2dec5-1ee2-44fa-bc99-bab2723cb712 (old id 1428219)
date added to LUP
2009-06-25 10:37:05
date last changed
2017-01-01 04:33:55
@article{acd2dec5-1ee2-44fa-bc99-bab2723cb712,
  abstract     = {Given an arbitrary real constant epsilon > 0, and a geometric graph G in d-dimensional Euclidean space with n points, O(n) edges, and constant dilation, our main result is a data structure that answers (1 + epsilon)-approximate shortest-path-length 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 shortest-path 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 shortest-path queries between vertices in a planar polygonal domain with "rounded" obstacles can be answered in constant time. Other applications include query versions of closest-pair 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 shortest-path-length 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         = {1549-6333},
  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},
}