Approximate distance queries in disk graphs

Martin Fürer, Shiva Prasad Kasiviswanathan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


We present efficient algorithms for approximately answering distance queries in disk graphs. Let G be a disk graph with n vertices and m edges. For any fixed ε > 0, we show that G can be preprocessed in O(m√nε-1 + mε-2 log S) time, constructing a data structure of size O(n3/2ε-1 + nε-2 log S), such that any subsequent distance query can be answered approximately in O(√nε-1-2log S) time. Here S is the ratio between the largest and smallest radius. The estimate produced is within an additive error which is only e times the longest edge on some shortest path. The algorithm uses an efficient subdivision of the plane to construct a sparse graph having many of the same distance properties as the input disk graph. Additionally, the sparse graph has a small separator decomposition, which is then used to answer distance queries. The algorithm extends naturally to the higher dimensional ball graphs.

Original languageEnglish (US)
Title of host publicationApproximation and Online Algorithms - 4th International Workshop, WAOA 2006, Revised Papers
PublisherSpringer Verlag
Number of pages14
ISBN (Print)9783540695134
StatePublished - 2007
Event4th Workshop on Approximation and Online Algorithms, WAOA 2006 - Zurich, Switzerland
Duration: Sep 14 2006Sep 15 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4368 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other4th Workshop on Approximation and Online Algorithms, WAOA 2006

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Approximate distance queries in disk graphs'. Together they form a unique fingerprint.

Cite this