2019/03/12 by Wang, Haitao, Xue, Jie · 3 citations
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1903.05255
We revisit a classical graph-theoretic problem, the single-source shortest-path (SSSP) problem, in weighted unit-disk graphs. We first propose an exact (and deterministic) algorithm which solves the problem in O(n log2 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 Jejčič [CGTA'15] which uses O(n1+δ) time and O(n1+δ) space (for any small constant δ>0) and the previous randomized algorithm by Kaplan et al. [SODA'17] which uses O(n log12+o(1) n) expected time and O(n log3 n) space. More specifically, we show that if the 2D offline insertion-only (additively-)weighted nearest-neighbor problem with k operations (i.e., insertions and queries) can be solved in f(k) time, then the SSSP problem in weighted unit-disk 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+ε)-approximate algorithm for the problem, using O(n log n + n log2(1/ε)) time and linear space. This improves the previous (1+ε)-approximate algorithm by Chan and Skrepetos [SoCG'18] which uses O((1/ε)2 n log n) time and O((1/ε)2 n) space. More specifically, we show that if the 2D offline insertion-only weighted nearest-neighbor problem with k1 operations in which at most k2 operations are insertions can be solved in f(k1,k2) time, then the (1+ε)-approximate SSSP problem in weighted unit-disk graphs can be solved in O(n log n+f(n,O(ε-2))) time. Because of the Ω(n log n)-time lower bound of the problem (even when approximation is allowed), both of our algorithms are almost optimal.