Approximate distance oracles for geometric graphs
(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}}, }