# Reverse Shortest Path Problem for Unit-Disk Graphs

Preprint · Haitao Wang, Yiming Zhao

- Archive id: arxiv:2104.14476
- Published: 2021-04-29
- arXiv: https://arxiv.org/abs/2104.14476
- Source URL: https://arxiv.org/abs/2104.14476
- PDF: https://arxiv.org/pdf/2104.14476
- Provenance: arxiv

## Abstract

Given a set P of n points in the plane, the unit-disk graph G\_{r}(P) with respect to a parameter r is an undirected graph whose vertex set is P such that an edge connects two points p, q \\in P if the Euclidean distance between p and q is at most r (the weight of the edge is 1 in the unweighted case and is the distance between p and q in the weighted case). Given a value λ\>0 and two points s and t of P, we consider the following reverse shortest path problem: computing the smallest r such that the shortest path length between s and t in G\_r(P) is at most λ. In this paper, we present an algorithm of O(\\lfloor λ\\rfloor \\cdot n \\log n) time and another algorithm of O(n^{5/4} \\log^{7/4} n) time for the unweighted case, as well as an O(n^{5/4} \\log^{5/2} n) time algorithm for the weighted case. We also consider the L\_1 version of the problem where the distance of two points is measured by the L\_1 metric; we solve the problem in O(n \\log^3 n) time for both the unweighted and weighted cases.

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