Approximate shortest paths and distance oracles in weighted unit-disk graphs

Timothy M. Chan, Dimitrios Skrepetos

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

Abstract

We present the first near-linear-time (1 + ϵ)-approximation algorithm for the diameter of a weighted unit-disk graph of n vertices, running in O (nlog2 n) time, for any constant ϵ > 0, improving the near-O n3/2)-time algorithm of Gao and Zhang [STOC 2003]. Using similar ideas, we can construct a (1 + ϵ)-approximate distance oracle for weighted unit-disk graphs with O(1) query time, with a similar improvement in the preprocessing time, from near O(n3/2) to O (n log3 n). We also obtain new results for a number of other related problems in the weighted unit-disk graph metric, such as the radius and bichromatic closest pair. As a further application, we use our new distance oracle, along with additional ideas, to solve the (1 + ϵ)-approximate all-pairs bounded-leg shortest paths problem for a set of n planar points, with near O (n2.579) preprocessing time, O (n2logn) space, and O (loglogn) query time, improving thus the near-cubic preprocessing bound by Roditty and Segal [SODA 2007].

Original languageEnglish (US)
Title of host publication34th International Symposium on Computational Geometry, SoCG 2018
EditorsCsaba D. Toth, Bettina Speckmann
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages241-2413
Number of pages2173
ISBN (Electronic)9783959770668
DOIs
StatePublished - Jun 1 2018
Event34th International Symposium on Computational Geometry, SoCG 2018 - Budapest, Hungary
Duration: Jun 11 2018Jun 14 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume99
ISSN (Print)1868-8969

Other

Other34th International Symposium on Computational Geometry, SoCG 2018
CountryHungary
CityBudapest
Period6/11/186/14/18

Keywords

  • Distance oracles
  • Planar graphs
  • Shortest paths
  • Unit-disk graphs

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Approximate shortest paths and distance oracles in weighted unit-disk graphs'. Together they form a unique fingerprint.

Cite this