2024/07/03 by Brewer, Bruce W., Wang, Haitao · 1 citation
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2407.03176
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 euv ∈ E between vertices u, v ∈ V if the Euclidean distance between u and v is at most 1. The weight of each edge euv 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 log2 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 log2 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.