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:
https://lup.lub.lu.se/record/633266
- author
- Gudmundsson, Joachim
; Levcopoulos, Christos
LU
; Narasimhan, Giri
and Smid, Michiel
- organization
- publishing date
- 2002
- 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
- 2022-01-29 21:31:00
@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}},
}