Chan, Timothy M. ;
Skrepetos, Dimitrios
Approximate Shortest Paths and Distance Oracles in Weighted UnitDisk Graphs
Abstract
We present the first nearlineartime (1 + epsilon)approximation algorithm for the diameter of a weighted unitdisk graph of n vertices, running in O(n log^2 n) time, for any constant epsilon>0, improving the nearO(n^{3/2})time algorithm of Gao and Zhang [STOC 2003]. Using similar ideas, we can construct a (1+epsilon)approximate distance oracle for weighted unitdisk graphs with O(1) query time, with a similar improvement in the preprocessing time, from near O(n^{3/2}) to O(n log^3 n). We also obtain new results for a number of other related problems in the weighted unitdisk 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 + epsilon)approximate allpairs boundedleg shortest paths problem for a set of n planar points, with near O(n^{2.579}) preprocessing time, O(n^2 log n) space, and O(log{log n}) query time, improving thus the nearcubic preprocessing bound by Roditty and Segal [SODA 2007].
BibTeX  Entry
@InProceedings{chan_et_al:LIPIcs:2018:8737,
author = {Timothy M. Chan and Dimitrios Skrepetos},
title = {{Approximate Shortest Paths and Distance Oracles in Weighted UnitDisk Graphs}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {24:124:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770668},
ISSN = {18688969},
year = {2018},
volume = {99},
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8737},
URN = {urn:nbn:de:0030drops87375},
doi = {10.4230/LIPIcs.SoCG.2018.24},
annote = {Keywords: shortest paths, distance oracles, unitdisk graphs, planar graphs}
}
2018
Keywords: 

shortest paths, distance oracles, unitdisk graphs, planar graphs 
Seminar: 

34th International Symposium on Computational Geometry (SoCG 2018)

Issue date: 

2018 
Date of publication: 

2018 