Line Intersection Searching Amid Unit Balls in 3-Space

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