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 ² n) time Wang and Xue, SoCG'19. The problem has an (n n) lower bound under the algebraic decision tree model. In this paper, we present an improved algorithm of O (n ² n / n) time (under the standard real RAM model). Furthermore, we show that the problem can be solved using O (n n) comparisons under the algebraic decision tree model, matching the (n n) lower bound.