Back to Search
Start Over
Approximate shortest paths and distance oracles in weighted unit-disk graphs
- 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
- Subjects :
- 060201 languages & linguistics
000 Computer science, knowledge, general works
TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
0602 languages and literature
Computer Science
0202 electrical engineering, electronic engineering, information engineering
020201 artificial intelligence & image processing
06 humanities and the arts
02 engineering and technology
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....c7495a973c3df1d242fa8ea948078453
- Full Text :
- https://doi.org/10.20382/jocg.v10i2a2