Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs

摘要

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 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 delta0) 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 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+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.