Back to Search Start Over

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

Authors :
Chan, Timothy M.
Skrepetos, Dimitrios
Publication Year :
2019
Publisher :
Journal of Computational Geometry, 2019.

Abstract

$\newcommand{\OO}[1]{O\left(#1\right)}\newcommand{\eps}{\varepsilon}$We present the first near-linear-time algorithm that computes a $(1+\eps)$-approximation of the diameter of a weighted unit-disk graph of $n$ vertices. Our algorithm requires $\OO{n \log^2 n}$ time for any constant $\eps>0$, so we considerably improve upon the near-$\OO{n^{3/2}}$-time algorithm of Gao and Zhang (2005). Using similar ideas we develop $(1+\eps)$-approximate \emph{distance oracles} of $\OO{1}$ query time with a likewise improvement in the preprocessing time, specifically from near $\OO{n^{3/2}}$ to $\OO{n \log^3 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+\eps)$-approximate \emph{all-pairs bounded-leg shortest paths\/} (apBLSP) problem for a set of $n$ planar points. Our data structure requires $\OO{n^2 \log n}$ space, $\OO{\log{\log n}}$ query time, and nearly $\OO{n^{2.579}}$ preprocessing time for any constant $\eps>0$, and is the first that breaks the near-cubic preprocessing time bound given by Roditty and Segal (2011).<br />Journal of Computational Geometry, Vol. 10 No. 2 (2019): Special Issue of Selected Papers from SoCG 2018

Details

Language :
English
Database :
OpenAIRE
Accession number :
edsair.doi.dedup.....c7495a973c3df1d242fa8ea948078453
Full Text :
https://doi.org/10.20382/jocg.v10i2a2