# Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs

Preprint · Haitao Wang, Jie Xue

- Archive id: arxiv:1903.05255
- Published: 2019-03-12
- arXiv: https://arxiv.org/abs/1903.05255
- Source URL: https://arxiv.org/abs/1903.05255
- PDF: https://arxiv.org/pdf/1903.05255
- Provenance: arxiv

## Abstract

We revisit a classical graph-theoretic problem, the \\textit{single-source shortest-path} (SSSP) problem, in weighted unit-disk graphs. We first propose an exact (and deterministic) algorithm which solves the problem in $O(n \\log^2 n)$ time using linear space, where $n$ is the number of the vertices of the graph. This significantly improves the previous deterministic algorithm by Cabello and Jejčič \[CGTA'15\] which uses $O(n^{1+δ})$ time and $O(n^{1+δ})$ space (for any small constant $δ\>0$) and the previous randomized algorithm by Kaplan et al. \[SODA'17\] which uses $O(n \\log^{12+o(1)} n)$ expected time and $O(n \\log^3 n)$ space. More specifically, we show that if the 2D offline insertion-only (additively-)weighted nearest-neighbor problem with $k$ operations (i.e., insertions and queries) can be solved in $f(k)$ time, then the SSSP problem in weighted unit-disk graphs can be solved in $O(n \\log n+f(n))$ time. Using the same framework with some new ideas, we also obtain a $(1+\\varepsilon)$-approximate algorithm for the problem, using $O(n \\log n + n \\log^2(1/\\varepsilon))$ time and linear space. This improves the previous $(1+\\varepsilon)$-approximate algorithm by Chan and Skrepetos \[SoCG'18\] which uses $O((1/\\varepsilon)^2 n \\log n)$ time and $O((1/\\varepsilon)^2 n)$ space. More specifically, we show that if the 2D offline insertion-only weighted nearest-neighbor problem with $k\_1$ operations in which at most $k\_2$ operations are insertions can be solved in $f(k\_1,k\_2)$ time, then the $(1+\\varepsilon)$-approximate SSSP problem in weighted unit-disk graphs can be solved in $O(n \\log n+f(n,O(\\varepsilon^{-2})))$ time. Because of the $Ω(n \\log n)$-time lower bound of the problem (even when approximation is allowed), both of our algorithms are almost optimal.

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