2026-08-18T13:47:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17855 2024-03-06T11:00:32Z ddc:004 open_access

Line Intersection Searching Amid Unit Balls in 3-Space Agarwal, Pankaj K. Ezra, Esther Intersection searching cylindrical range searching partition trees union of cylinders Let ℬ be a set of n unit balls in ℝ³. We present a linear-size data structure for storing ℬ that can determine in O^*(n^{1/2}) time whether a query line intersects any ball of ℬ 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 ℒ be a set of n lines in ℝ³. We preprocess ℒ, 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 ℒ, or report all k such lines in additional O(k) time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pankaj K. Agarwal and Esther Ezra 2023 Is Part Of LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2023.5 urn:nbn:de:0030-drops-178559 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.5 eng https://creativecommons.org/licenses/by/4.0/legalcode