Advanced

Approximate distance oracles for geometric graphs

Gudmundsson, Joachim ; Levcopoulos, Christos LU ; Narasimhan, Giri and Smid, Michiel (2002) Symposium on Discrete Algorithms, 2002 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
; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
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
conference location
San Francisco, California, United States
conference dates
2002-01-06 - 2002-01-08
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
2016-04-04 11:12:07
date last changed
2020-11-22 03:57:46
@inproceedings{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},
  booktitle    = {Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms},
  isbn         = {0-89871-513-X},
  language     = {eng},
  pages        = {828--837},
  publisher    = {Society for Industrial and Applied Mathematics},
  title        = {Approximate distance oracles for geometric graphs},
  url          = {http://dx.doi.org/10.1145/545381.545489},
  doi          = {10.1145/545381.545489},
  year         = {2002},
}