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

Timothy M. Chan, Dimitrios Skrepetos

Research output: Contribution to journalArticlepeer-review

Abstract

We present the first near-linear-time algorithm that computes a (1 + ε)- approximation of the diameter of a weighted unit-disk graph of n vertices. Our algorithm requires O (n log2 n) time for any constant ε > 0, so we considerably improve upon the near-O (n3/2) -time algorithm of Gao and Zhang [17]. Using similar ideas we develop (1+ε)- approximate distance oracles of O (1) query time with a likewise improvement in the preprocessing time, specifically from near O (n3/2) to O (n log3 n). We also obtain similar new results for a number of related problems in the weighted unit-disk graph metric such as the radius and the bichromatic closest pair. As a further application we employ our distance oracle, along with additional ideas, to solve the (1 + ε)-approximate all-pairs bounded-leg shortest paths (apBLSP) problem for a set of n planar points. Our data structure requires O (n2 log n) space, O (log log n) query time, and nearly O (n2:579) preprocessing time for any constant ε > 0, and is the first that breaks the near-cubic preprocessing time bound given by Roditty and Segal [31].

Original languageEnglish (US)
Pages (from-to)3-20
Number of pages18
JournalJournal of Computational Geometry
Volume10
Issue number2
DOIs
StatePublished - 2019

ASJC Scopus subject areas

  • Geometry and Topology
  • Computer Science Applications
  • Computational Theory and Mathematics

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