Theory Seminar: Please join us on April 28th at 11AM in Siebel 3401 where Zhengcheng Huang will give a talk, “Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique”. Please see the abstract below:
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 $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})$.