Reverse Shortest Path Problem for Unit-Disk Graphs

Given a set P of n points in the plane, a unit-disk graph Gr(P) with respect to a radius r is an undirected graph whose vertex set is P such that an edge connects two points p, q ∈ P is the number of edges of the path. Given a value λ \u3e 0 and two points s and t of P, we consider the following reverse shortest path problem: finding the smallest r such that the shortest path length between s and t in Gr(P) is at most λ. It was known previously that the problem can be solved in O(n5/4log2n) time