Approximate distance oracles revisited
(2002) 13th International Symposium, ISAAC 2002 2518. p.357-368- Abstract
- Let G be a geometric t-spanner in E-d with n vertices and m edges, where t is a constant. We show that G can be preprocessed in O(m log n) time, such that (1 + epsilon)-approximate shortest-path queries in G can be answered 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/311041
- author
- Gudmundsson, J ; Levcopoulos, Christos LU ; Narasimhan, G and Smid, M
- organization
- publishing date
- 2002
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Algorithms and Computation, Proceedings / Lecture Notes in Computer Science
- volume
- 2518
- pages
- 357 - 368
- publisher
- Springer
- conference name
- 13th International Symposium, ISAAC 2002
- conference location
- Vancouver, BC, Canada
- conference dates
- 2002-11-21 - 2002-11-23
- external identifiers
-
- wos:000182826400032
- scopus:84878636580
- ISSN
- 1611-3349
- 0302-9743
- language
- English
- LU publication?
- yes
- id
- 7b2840ab-fcad-4643-9206-12687648ef68 (old id 311041)
- alternative location
- http://www.springerlink.com/content/91wdneley60rgv1f
- date added to LUP
- 2016-04-01 12:07:49
- date last changed
- 2024-01-08 09:25:47
@inproceedings{7b2840ab-fcad-4643-9206-12687648ef68, abstract = {{Let G be a geometric t-spanner in E-d with n vertices and m edges, where t is a constant. We show that G can be preprocessed in O(m log n) time, such that (1 + epsilon)-approximate shortest-path queries in G can be answered in O(1) time. The data structure uses O(n log n) space.}}, author = {{Gudmundsson, J and Levcopoulos, Christos and Narasimhan, G and Smid, M}}, booktitle = {{Algorithms and Computation, Proceedings / Lecture Notes in Computer Science}}, issn = {{1611-3349}}, language = {{eng}}, pages = {{357--368}}, publisher = {{Springer}}, title = {{Approximate distance oracles revisited}}, url = {{http://www.springerlink.com/content/91wdneley60rgv1f}}, volume = {{2518}}, year = {{2002}}, }