Abstract
We revisit a classical graphtheoretic problem, the singlesource shortestpath (SSSP) problem, in weighted unitdisk graphs. We first propose an exact (and deterministic) algorithm which solves the problem in O(n log^2 n) time using linear space, where n is the number of the vertices of the graph. This significantly improves the previous deterministic algorithm by Cabello and Jejcic [CGTA'15] which uses O(n^{1+delta}) time and O(n^{1+delta}) space (for any small constant delta>0) and the previous randomized algorithm by Kaplan et al. [SODA'17] which uses O(n log^{12+o(1)} n) expected time and O(n log^3 n) space. More specifically, we show that if the 2D offline insertiononly (additively)weighted nearestneighbor problem with k operations (i.e., insertions and queries) can be solved in f(k) time, then the SSSP problem in weighted unitdisk graphs can be solved in O(n log n+f(n)) time. Using the same framework with some new ideas, we also obtain a (1+epsilon)approximate algorithm for the problem, using O(n log n + n log^2(1/epsilon)) time and linear space. This improves the previous (1+epsilon)approximate algorithm by Chan and Skrepetos [SoCG'18] which uses O((1/epsilon)^2 n log n) time and O((1/epsilon)^2 n) space. Because of the Omega(n log n)time lower bound of the problem (even when approximation is allowed), both of our algorithms are almost optimal.
BibTeX  Entry
@InProceedings{wang_et_al:LIPIcs:2019:10464,
author = {Haitao Wang and Jie Xue},
title = {{NearOptimal Algorithms for Shortest Paths in Weighted UnitDisk Graphs}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {60:160:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771047},
ISSN = {18688969},
year = {2019},
volume = {129},
editor = {Gill Barequet and Yusu Wang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10464},
URN = {urn:nbn:de:0030drops104649},
doi = {10.4230/LIPIcs.SoCG.2019.60},
annote = {Keywords: Singlesource shortest paths, Weighted unitdisk graphs, Geometric graph algorithms}
}
Keywords: 

Singlesource shortest paths, Weighted unitdisk graphs, Geometric graph algorithms 
Collection: 

35th International Symposium on Computational Geometry (SoCG 2019) 
Issue Date: 

2019 
Date of publication: 

11.06.2019 