An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs

Abstract

Given in the plane a set $S$ of $n$ points and a set of disks centered at these points, the disk graph $G(S)$ induced by these disks has vertex set $S$ and an edge between two vertices if their disks intersect. Note that the disks may have different radii. We consider the problem of computing shortest paths from a source point $s\in S$ to all vertices in $G(S)$ where the length of a path in $G(S)$ is defined as the number of edges in the path. The previously best algorithm solves the problem in $O(n\log^2 n)$ time. A lower bound of $Ω(n\log n)$ is also known for this problem under the algebraic decision tree model. In this paper, we present an $O(n\log n)$ time algorithm, which matches the lower bound and thus is optimal. Another virtue of our algorithm is that it is quite simple.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.