Approximate distance oracles for geometric graphs

Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan, Michiel Smid

    Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceedingResearchpeer-review

    37 Citations (SciVal)

    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.
    Original languageEnglish
    Title of host publicationProceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms
    PublisherSociety for Industrial and Applied Mathematics
    Pages828-837
    ISBN (Print)0-89871-513-X
    DOIs
    Publication statusPublished - 2002
    EventSymposium on Discrete Algorithms, 2002 - San Francisco, California, United States
    Duration: 2002 Jan 62002 Jan 8
    Conference number: 13

    Conference

    ConferenceSymposium on Discrete Algorithms, 2002
    Abbreviated titleACM-SIAM
    Country/TerritoryUnited States
    CitySan Francisco, California
    Period2002/01/062002/01/08

    Subject classification (UKÄ)

    • Computer Science

    Fingerprint

    Dive into the research topics of 'Approximate distance oracles for geometric graphs'. Together they form a unique fingerprint.

    Cite this