2026-07-23T15:16:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24953 2026-02-09T08:02:32Z ddc:004 open_access

BFS and Reverse Shortest Paths for Ball Intersection Graphs in Three and Higher Dimensions Katz, Matthew J. Saban, Rachel Sharir, Micha Computational geometry reverse shortest paths breadth-first search shrink-and-bifurcate intersection graphs Let ℬ be a collection of n arbitrary balls in ℝ³, and let G₀(ℬ) be their intersection graph. We provide an algorithm for performing BFS on G₀(ℬ), which runs in O^*(n^{4/3}) time, where the O^*(⋅) notation hides subpolynomial factors. For r ≥ 0, let G_r(ℬ) be the intersection graph of the set ℬ_r = {B+r ∣ B ∈ ℬ}, where B+r is the ball concentric with B whose radius is larger by r than the radius of B. We provide an efficient algorithm for the reverse shortest path (RSP) problem, where we are given two designated balls B_s, B_t of ℬ and a parameter 0 < λ < n, and seek the smallest value r^* for which G_{r^*}(ℬ) contains a path from B_s to B_t of at most λ edges. For the special case of congruent balls (equivalently, for points in ℝ³), the algorithm runs in O^*(n^{29/21}) ≈ O^*(n^{1.381}) time. For the general case, the algorithm runs in O^*(n^{56/39}) ≈ O^*(n^{1.436}) time. We also extend the technique to handle other measures of expansion and higher dimensions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthew J. Katz and Rachel Saban and Micha Sharir 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.45 urn:nbn:de:0030-drops-249535 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.45 eng https://creativecommons.org/licenses/by/4.0/legalcode