# Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique

Preprint · Timothy M. Chan, Zhengcheng Huang

- Archive id: arxiv:2504.06434
- Published: 2025-04-08
- arXiv: https://arxiv.org/abs/2504.06434
- Source URL: https://arxiv.org/abs/2504.06434
- PDF: https://arxiv.org/pdf/2504.06434
- Provenance: arxiv

## Abstract

In a series of papers, Avraham, Filtser, Kaplan, Katz, and Sharir (SoCG'14), Kaplan, Katz, Saban, and Sharir (ESA'23), and Katz, Saban, and Sharir (ESA'24) studied a class of geometric optimization problems -- including reverse shortest path in unweighted and weighted unit-disk graphs, discrete Fréchet distance with one-sided shortcuts, and reverse shortest path in visibility graphs on 1.5-dimensional terrains -- for which standard parametric search does not work well due to a lack of efficient parallel algorithms for the corresponding decision problems. The best currently known algorithms for all the above problems run in $O^\*(n^{6/5})=O^\*(n^{1.2})$ time (ignoring subpolynomial factors), and they were obtained using a technique called \\emph{shrink-and-bifurcate}. We improve the running time to $\\tilde{O}(n^{8/7}) \\approx O(n^{1.143})$ for these problems. Furthermore, specifically for reverse shortest path in unweighted unit-disk graphs, we improve the running time further to $\\tilde{O}(n^{9/8})=\\tilde{O}(n^{1.125})$.

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