2026-09-05T11:57:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25829 2026-06-23T12:59:09Z ddc:004 open_access

Shortest Paths in Geodesic Unit-Disk Graphs Brewer, Bruce W. Wang, Haitao unit-disk graph geodesic distance shortest paths geodesic Voronoi diagrams range emptiness queries dynamic data structures Let S be a set of n points in a polygon P with m vertices. The geodesic unit-disk graph G(S) induced by S has vertex set S and contains an edge between two vertices whenever their geodesic distance in P is at most one. In the weighted version, each edge is assigned weight equal to the geodesic distance between its endpoints; in the unweighted version, every edge has weight 1. Given a source point s ∈ S, we study the problem of computing shortest paths from s to all vertices of G(S). To the best of our knowledge, this problem has not been investigated previously. A naive approach constructs G(S) explicitly and then applies a standard shortest path algorithm for general graphs, but this requires quadratic time in the worst case, since G(S) may contain Ω(n²) edges. In this paper, we give the first subquadratic-time algorithms for this problem. For the weighted case, when P is a simple polygon, we obtain an O(m + n log³ n log² m)-time algorithm. For the unweighted case, we provide an O(m + n log n log² m)-time algorithm for simple polygons, and an O(√n (n+m)log(n+m))-time algorithm for polygons with holes. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bruce W. Brewer and Haitao Wang 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.23 urn:nbn:de:0030-drops-258297 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.23 eng https://creativecommons.org/licenses/by/4.0/legalcode