2025/04/08 by Chan, Timothy M., Huang, Zhengcheng · 2 citations
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2504.06434
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^*(n6/5)=O^*(n1.2) time (ignoring subpolynomial factors), and they were obtained using a technique called shrink-and-bifurcate. We improve the running time to O(n8/7) ≈ O(n1.143) for these problems. Furthermore, specifically for reverse shortest path in unweighted unit-disk graphs, we improve the running time further to O(n9/8)=O(n1.125).