Du är här

Approximate distance oracles for geometric spanners

Författare:
Publiceringsår: 2008
Språk: Engelska
Publikation/Tidskrift/Serie: ACM transactions on algorithms
Volym: 4
Nummer: 1
Dokumenttyp: Artikel
Förlag: ACM

Sammanfattning

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.

Disputation

Nyckelord

  • Technology and Engineering
  • geometric graphs
  • approximation algorithm
  • Shortest paths
  • computational geometry
  • spanners

Övrigt

Published
  • VR 2005-4085
Yes
  • ISSN: 1549-6325

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen

LERU logo U21 logo