An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs

Let V be a set of n points in the plane. The unit-disk graph $G = (V, E)$ has vertex set V and an edge eᵤᵥ ∈ E between vertices u, v ∈ V if the Euclidean distance between u and v is at most 1. The weight of each edge eᵤᵥ is the Euclidean distance between u and v. Given V and a source point s∈ V, we consider the problem of computing shortest paths in G from s to all other vertices. The previously best algorithm for this problem runs in O(n log² n) time [Wang and Xue, SoCG'19]. The problem has an Ω(nlog n) lower bound under the algebraic decision tree model. In this paper, we present an improved algorithm of O(n log² n / log log n) time (under the standard real RAM model). Furthermore, we show that the problem can be solved using O(nlog n) comparisons under the algebraic decision tree model, matching the Ω(nlog n) lower bound.