2026-07-21T19:26:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18754 2024-03-06T11:02:38Z ddc:004 open_access

Improved Algorithms for Distance Selection and Related Problems Wang, Haitao Zhao, Yiming Geometric optimization distance selection Fréchet distance range searching In this paper, we propose new techniques for solving geometric optimization problems involving interpoint distances of a point set in the plane. Given a set P of n points in the plane and an integer 1 ≤ k ≤ binom(n,2), the distance selection problem is to find the k-th smallest interpoint distance among all pairs of points of P. The previously best deterministic algorithm solves the problem in O(n^{4/3} log² n) time [Katz and Sharir, 1997]. In this paper, we improve their algorithm to O(n^{4/3} log n) time. Using similar techniques, we also give improved algorithms on both the two-sided and the one-sided discrete Fréchet distance with shortcuts problem for two point sets in the plane. For the two-sided problem (resp., one-sided problem), we improve the previous work [Avraham, Filtser, Kaplan, Katz, and Sharir, 2015] by a factor of roughly log²(m+n) (resp., (m+n)^ε), where m and n are the sizes of the two input point sets, respectively. Other problems whose solutions can be improved by our techniques include the reverse shortest path problems for unit-disk graphs. Our techniques are quite general and we believe they will find many other applications in future. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haitao Wang and Yiming Zhao 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.101 urn:nbn:de:0030-drops-187544 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.101 eng https://creativecommons.org/licenses/by/4.0/legalcode