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 for geometric graphs

På svenska

Author

Summary, in English

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.

Department/s

  • Computer Science

Publishing year

2002

Language

English

Pages

828-837

Publication/Series

Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms

Document type

Conference paper

Publisher

Society for Industrial and Applied Mathematics

Topic

  • Computer Science

Conference name

Symposium on Discrete Algorithms, 2002

Conference date

2002-01-06 - 2002-01-08

Conference place

San Francisco, California, United States

Status

Published

ISBN/ISSN/Other

  • ISBN: 0-89871-513-X