DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2026.23

Shortest Paths in Geodesic Unit-Disk Graphs

Authors: Bruce W. Brewer and Haitao Wang

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

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.

Cite as

Bruce W. Brewer and Haitao Wang. Shortest Paths in Geodesic Unit-Disk Graphs. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brewer_et_al:LIPIcs.SoCG.2026.23,
  author =	{Brewer, Bruce W. and Wang, Haitao},
  title =	{{Shortest Paths in Geodesic Unit-Disk Graphs}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.23},
  URN =		{urn:nbn:de:0030-drops-258297},
  doi =		{10.4230/LIPIcs.SoCG.2026.23},
  annote =	{Keywords: unit-disk graph, geodesic distance, shortest paths, geodesic Voronoi diagrams, range emptiness queries, dynamic data structures}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.31

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs

Authors: Bruce W. Brewer and Haitao Wang

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

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 ∈ 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.

Cite as

Bruce W. Brewer and Haitao Wang. An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 31:1-31:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{brewer_et_al:LIPIcs.ESA.2025.31,
  author =	{Brewer, Bruce W. and Wang, Haitao},
  title =	{{An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{31:1--31:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.31},
  URN =		{urn:nbn:de:0030-drops-244997},
  doi =		{10.4230/LIPIcs.ESA.2025.31},
  annote =	{Keywords: disk graphs, weighted Voronoi diagrams, shortest paths}
}

Search Results

Documents authored by Brewer, Bruce W.

Shortest Paths in Geodesic Unit-Disk Graphs

Abstract

Cite as

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message