Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs
share
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 ^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 Jejčič [CGTA'15] which uses O(n^1+δ) time and O(n^1+δ) space (for any small constant δ>0) and the previous randomized algorithm by Kaplan et al. [SODA'17] which uses O(n ^12+o(1) n) expected time and O(n ^3 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 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 n + n ^2(1/ε)) time and linear space. This improves the previous (1+ε)-approximate algorithm by Chan and Skrepetos [SoCG'18] which uses O((1/ε)^2 n n) time and O((1/ε)^2 n) space. More specifically, we show that if the 2D offline insertion-only weighted nearest-neighbor problem with k_1 operations in which at most k_2 operations are insertions can be solved in f(k_1,k_2) time, then the (1+ε)-approximate SSSP problem in weighted unit-disk graphs can be solved in O(n n+f(n,O(ε^-2))) time. Because of the Ω(n n)-time lower bound of the problem (even when approximation is allowed), both of our algorithms are almost optimal.
READ FULL TEXT