Reverse Shortest Path Problem in Weighted Unit-Disk Graphs

Given a set P of n points in the plane, a unit-disk graph Gr(P) with respect to a parameter r is an undirected graph whose vertex set is P such that an edge connects two points p,q∈P if the (Euclidean) distance between p and q is at most r (the weight of the edge is 1 in the unweighted case and is the distance between p and q in the weighted case). Given a value λ\u3e0 and two points s and t of P, we consider the following reverse shortest path problem: Compute the smallest r such that the shortest path length between s and t in Gr(P) is at most λ. In this paper, we study the weighted case and present an O(n5/4log5/2n) time algorithm. We also consider the L1 version of the problem where the distance of two points is measured by the L1 metric; we solve the problem in O(nlog3n) time for both the unweighted and weighted cases