Line Intersection Searching Amid Unit Balls in 3-Space
Pankaj K. Agarwal, Esther E. Ezra · Algorithmica · 2024
Let $$\mathscr {B}$$ be a set of n unit balls in $${\mathbb {R}}^3$$ . We present a linear-size data structure for storing $$\mathscr {B}$$ that can determine in $$O^*(\sqrt{n})$$ time whether a query line intersects any ball of $$\mathscr {B}$$ and report all k such balls in additional O(k) time. The data structure can be constructed in $$O(n\log n)$$ time. (The $$O^*(\cdot )$$ notation hides subpolynomial factors, e.g., of the form $$O(n^{{\varepsilon }})$$ , for arbitrarily small $${\varepsilon }> 0$$ , and their coefficients which depend on $${\varepsilon }$$ .) We also consider the dual problem: Let $$\mathscr {L}$$ be a set of n lines in $${\mathbb {R}}^3$$ . We preprocess $$\mathscr {L}$$ , in $$O^*(n^2)$$ time, into a data structure of size $$O^*(n^2)$$ that can determine in $$O(\log {n})$$ time whether a query unit ball intersects any line of $$\mathscr {L}$$ , or report all k such lines in additional O(k) time.