The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Approximate distance oracles revisited

På svenska

Author

Summary, in English

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.

Department/s

  • Computer Science

Publishing year

2002

Language

English

Pages

357-368

Publication/Series

Algorithms and Computation, Proceedings / Lecture Notes in Computer Science

Volume

2518

Document type

Conference paper

Publisher

Springer

Topic

  • Computer Science

Conference name

13th International Symposium, ISAAC 2002

Conference date

2002-11-21 - 2002-11-23

Conference place

Vancouver, BC, Canada

Status

Published

ISBN/ISSN/Other

  • ISSN: 1611-3349
  • ISSN: 0302-9743