{"ID":2896814,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.05569","arxiv_id":"2507.05569","title":"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.","short_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 sour...","url_abs":"https://arxiv.org/abs/2507.05569","url_pdf":"https://arxiv.org/pdf/2507.05569v2","authors":"[\"Bruce W. Brewer\",\"Haitao Wang\"]","published":"2025-07-08T01:13:49Z","proceeding":"cs.CG","tasks":"[\"cs.CG\",\"cs.DS\"]","methods":"[]","has_code":false}