Advanced

Approximate distance oracles for geometric graphs

Gudmundsson, Joachim; Levcopoulos, Christos LU ; Narasimhan, Giri and Smid, Michiel (2002) Symposium on Discrete Algorithms, 2002 In Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms p.828-837
Abstract
Given a geometric t-spanner graph G in Ed with n points and m edges, with edge lengths that lie within a polynomial (in n) factor of each other. Then, after O(m+n log n) preprocessing, we present an approximation scheme to answer (1+ε)-approximate shortest path queries in O(1) time. The data structure uses O(n log n) space.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms
pages
828 - 837
publisher
Society for Industrial and Applied Mathematics
conference name
Symposium on Discrete Algorithms, 2002
external identifiers
  • WOS:000177258600108
  • Scopus:84968754795
ISBN
0-89871-513-X
DOI
10.1145/545381.545489
language
English
LU publication?
yes
id
95ed6c67-7c64-4a65-b3d2-4d37e0ccd89c (old id 633266)
date added to LUP
2007-11-28 14:58:03
date last changed
2016-10-13 04:44:27
@misc{95ed6c67-7c64-4a65-b3d2-4d37e0ccd89c,
  abstract     = {Given a geometric t-spanner graph G in Ed with n points and m edges, with edge lengths that lie within a polynomial (in n) factor of each other. Then, after O(m+n log n) preprocessing, we present an approximation scheme to answer (1+ε)-approximate shortest path queries in O(1) time. The data structure uses O(n log n) space.},
  author       = {Gudmundsson, Joachim and Levcopoulos, Christos and Narasimhan, Giri and Smid, Michiel},
  isbn         = {0-89871-513-X},
  language     = {eng},
  pages        = {828--837},
  publisher    = {ARRAY(0xce16320)},
  series       = {Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms},
  title        = {Approximate distance oracles for geometric graphs},
  url          = {http://dx.doi.org/10.1145/545381.545489},
  year         = {2002},
}