# An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs

Preprint · Bruce W. Brewer, Haitao Wang

- Archive id: arxiv:2507.05569
- Published: 2025-07-08
- arXiv: https://arxiv.org/abs/2507.05569
- Source URL: https://arxiv.org/abs/2507.05569
- PDF: https://arxiv.org/pdf/2507.05569
- Provenance: arxiv

## 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 reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.