Line Intersection Searching Amid Unit Balls in 3-Space

Let B be a set of n unit balls in R³. We present a linear-size data structure for storing B that can determine in (Equation presented) time whether a query line intersects any ball of 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^∗(·) notation hides subpolynomial factors, e.g., of the form O(n^ε), for arbitrarily small ε > 0, and their coefficients which depend on ε.) We also consider the dual problem: Let L be a set of n lines in R³. We preprocess L, in O^∗(n²) time, into a data structure of size O^∗(n²) that can determine in O^∗(1) time whether a query unit ball intersects any line of L, or report all k such lines in additional O(k) time.

Duke Scholars

Author Pankaj K. Agarwal Computer Science