2026-07-20T07:31:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24499 2025-12-16T14:00:01Z ddc:004 open_access

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs Brewer, Bruce W. Wang, Haitao disk graphs weighted Voronoi diagrams shortest paths 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 ∈ 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(nlog² n) time. A lower bound of Ω(nlog n) is also known for this problem under the algebraic decision tree model. In this paper, we present an O(nlog n) time algorithm, which matches the lower bound and thus is optimal. Another virtue of our algorithm is that it is quite simple. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bruce W. Brewer and Haitao Wang 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.31 urn:nbn:de:0030-drops-244997 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.31 eng https://creativecommons.org/licenses/by/4.0/legalcode