Abstract
Let S be a set of n geometric objects of constant complexity (e.g., points, line segments, disks, ellipses) in ℝ², and let ϱ: S× S → ℝ_{≥ 0} be a distance function on S. For a parameter r ≥ 0, we define the proximity graph G(r) = (S,E) where E = {(e₁,e₂) ∈ S×S ∣ e₁≠e₂, ϱ(e₁,e₂) ≤ r}. Given S, s,t ∈ S, and an integer k ≥ 1, the reverseshortestpath (RSP) problem asks for computing the smallest value r^* ≥ 0 such that G(r^*) contains a path from s to t of length at most k.
In this paper we present a general randomized technique that solves the RSP problem efficiently for a large family of geometric objects and distance functions. Using standard, and sometimes more involved, semialgebraic rangesearching techniques, we first give an efficient algorithm for the decision problem, namely, given a value r ≥ 0, determine whether G(r) contains a path from s to t of length at most k. Next, we adapt our decision algorithm and combine it with a randomsampling method to compute r^*, by efficiently performing a binary search over an implicit set of O(n²) candidate values that contains r^*.
We illustrate the versatility of our general technique by applying it to a variety of geometric proximity graphs. For example, we obtain (i) an O^*(n^{4/3}) expectedtime randomized algorithm (where O^*(⋅) hides polylog(n) factors) for the case where S is a set of pairwisedisjoint line segments in ℝ² and ϱ(e₁,e₂) = min_{x ∈ e₁, y ∈ e₂} ‖xy‖ (where ‖⋅‖ is the Euclidean distance), and (ii) an O^*(n+m^{4/3}) expectedtime randomized algorithm for the case where S is a set of m points lying on an xmonotone polygonal chain T with n vertices, and ϱ(p,q), for p,q ∈ S, is the smallest value h such that the points p' := p+(0,h) and q' := q+(0,h) are visible to each other, i.e., all points on the segment p'q' lie above or on the polygonal chain T.
BibTeX  Entry
@InProceedings{agarwal_et_al:LIPIcs.ISAAC.2022.42,
author = {Agarwal, Pankaj K. and Katz, Matthew J. and Sharir, Micha},
title = {{On Reverse Shortest Paths in Geometric Proximity Graphs}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {42:142:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772587},
ISSN = {18688969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17327},
URN = {urn:nbn:de:0030drops173277},
doi = {10.4230/LIPIcs.ISAAC.2022.42},
annote = {Keywords: Geometric optimization, proximity graphs, semialgebraic range searching, reverse shortest path}
}
Keywords: 

Geometric optimization, proximity graphs, semialgebraic range searching, reverse shortest path 
Collection: 

33rd International Symposium on Algorithms and Computation (ISAAC 2022) 
Issue Date: 

2022 
Date of publication: 

14.12.2022 