# An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs

Preprint · Bruce W. Brewer, Haitao Wang

- Archive id: arxiv:2407.03176
- Published: 2024-07-03
- arXiv: https://arxiv.org/abs/2407.03176
- Source URL: https://arxiv.org/abs/2407.03176
- PDF: https://arxiv.org/pdf/2407.03176
- Provenance: arxiv

## Abstract

Let $V$ be a set of $n$ points in the plane. The unit-disk graph $G = (V, E)$ has vertex set $V$ and an edge $e\_{uv} \\in E$ between vertices $u, v \\in V$ if the Euclidean distance between $u$ and $v$ is at most 1. The weight of each edge $e\_{uv}$ is the Euclidean distance between $u$ and $v$. Given $V$ and a source point $s\\in V$, we consider the problem of computing shortest paths in $G$ from $s$ to all other vertices. The previously best algorithm for this problem runs in $O(n \\log^2 n)$ time \[Wang and Xue, SoCG'19\]. The problem has an $Ω(n\\log n)$ lower bound under the algebraic decision tree model. In this paper, we present an improved algorithm of $O(n \\log^2 n / \\log \\log n)$ time (under the standard real RAM model). Furthermore, we show that the problem can be solved using $O(n\\log n)$ comparisons under the algebraic decision tree model, matching the $Ω(n\\log n)$ lower bound.

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