{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreidqqb333b4dehenxrttx55fph4ajyf3loiitnlusfo6agg626wlge",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mhzkef2k6qa2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.24872v1",
  "publishedAt": "2026-03-27T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Bruce W. Brewer",
    "Haitao Wang"
  ],
  "textContent": "**Authors:** Bruce W. Brewer, Haitao Wang\n\nLet $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 \\in 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^2)$ 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^{2} n \\log^{2} m)$-time algorithm. For the unweighted case, we provide an $O(m + n \\log n \\log^{2} m)$-time algorithm for simple polygons, and an $O(\\sqrt{n} (n+m)\\log(n+m))$-time algorithm for polygons with holes. To achieve these results, we develop a data structure for deletion-only geodesic unit-disk range emptiness queries, as well as a data structure for constructing implicit additively weighted geodesic Voronoi diagrams in simple polygons. In addition, we propose a dynamic data structure that extends Bentley's logarithmic method from insertions to priority-queue updates, namely insertion and delete-min operations. These results may be of independent interest.",
  "title": "Shortest Paths in Geodesic Unit-Disk Graphs"
}