2026-07-21T20:02:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23184 2025-10-02T12:42:17Z ddc:004 open_access

Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-And-Bifurcate Technique Chan, Timothy M. Huang, Zhengcheng Geometric optimization problems parametric search shortest path disk graphs Fréchet distance visibility distance selection randomized algorithms 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 shrink-and-bifurcate. We improve the running time to Õ(n^{8/7}) ≈ 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 Õ(n^{9/8}) = Õ(n^{1.125}). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothy M. Chan and Zhengcheng Huang 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.32 urn:nbn:de:0030-drops-231845 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.32 eng https://creativecommons.org/licenses/by/4.0/legalcode