Document Open Access Logo

Line Intersection Searching Amid Unit Balls in 3-Space

Authors Pankaj K. Agarwal , Esther Ezra

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2023.5.pdf
  • Filesize: 0.79 MB
  • 14 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Theory of computation → Computational geometry
Keywords
  • Intersection searching
  • cylindrical range searching
  • partition trees
  • union of cylinders

Metrics

Abstract

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.

Cite As Get BibTex

Pankaj K. Agarwal and Esther Ezra. Line Intersection Searching Amid Unit Balls in 3-Space. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.SoCG.2023.5

Author Details

Pankaj K. Agarwal
  • Department of Computer Science, Duke University, Durham, NC, USA
Esther Ezra
  • School of Computer Science, Bar Ilan University, Ramat Gan, Israel

Funding

  • Agarwal, Pankaj K.: Work partially supported by NSF grants IIS-18-14493, CCF-20-07556, and CCF-22-23870.
  • Ezra, Esther: Work partially supported by Grants 824/17 and 800/22 from the Israel Science Foundation.

References

  1. Pankaj K. Agarwal. Range searching,. In J. E. Goodman, J. O'Rourke, and C. D. Tóth, editors, Handbook of Discrete and Computational Geometry, chapter 40, pages 1057-1092. Chapman and Hall/CRC, third edition, 2017. URL: https://www.taylorfrancis.com/chapters/edit/10.1201/9781315119601-40/range-searching-pankaj-agarwal.
  2. Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Matthew J. Katz, and Micha Sharir. Intersection queries for flat semi-algebraic objects in three dimensions and related problems. In Proc. 38th Int. Sympos. Comput. Geom., volume 224 of LIPIcs, pages 4:1-4:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.SoCG.2022.4.
  3. Pankaj K. Agarwal and Je Erickson. Geometric range searching and its relatives. In B. Chazelle, J. E. Goodman, and R. Pollack, editors, Advances in Discrete and Computational Geometry, pages 1-56. Amer. Math. Soc., 2007. Google Scholar
  4. Pankaj K. Agarwal and Jirí Matousek. On range searching with semialgebraic sets. Discret. Comput. Geom., 11:393-418, 1994. URL: https://doi.org/10.1007/BF02574015.
  5. Timothy M. Chan. Optimal partition trees. Discret. Comput. Geom., 47(4):661-690, 2012. URL: https://doi.org/10.1007/s00454-012-9410-z.
  6. Bernard Chazelle. Cutting hyperplanes for divide-and-conquer. Discret. Comput. Geom., 9:145-158, 1993. URL: https://doi.org/10.1007/BF02189314.
  7. David P. Dobkin and Herbert Edelsbrunner. Space searching for intersecting objects. J. Algorithms, 8(3):348-361, 1987. URL: https://doi.org/10.1016/0196-6774(87)90015-0.
  8. Esther Ezra and Micha Sharir. On ray shooting for triangles in 3-space and related problems. SIAM J. Comput., 51(4):1065-1095, 2022. URL: https://doi.org/10.1137/21m1408245.
  9. Larry Guth. Polynomial partitioning for a set of varieties. Math. Proc. Camb. Phil. Soc., 159:459-469, 2015. URL: http://hdl.handle.net/1721.1/110285.
  10. Vladlen Koltun. Almost tight upper bounds for vertical decompositions in four dimensions. J. ACM, 51(5):699-730, 2004. URL: https://doi.org/10.1145/1017460.1017461.
  11. Jirí Matousek. Reporting points in halfspaces. Comput. Geom., 2:169-186, 1992. URL: https://doi.org/10.1016/0925-7721(92)90006-E.
  12. Shai Mohaban and Micha Sharir. Ray shooting amidst spheres in three dimensions and related problems. SIAM J. Comput., 26(3):654-674, 1997. URL: https://doi.org/10.1137/S0097539793252080.
  13. Marco Pellegrini. Ray shooting on triangles in 3-space. Algorithmica, 9(5):471-494, 1993. URL: https://doi.org/10.1007/BF01187036.
  14. Marco Pellegrini. Ray shooting and lines in space. In Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Tóth, editors, Handbook of Discrete and Computational Geometry, pages 1093-1112. CRC Press, third edition edition, 2017. Google Scholar
  15. Micha Sharir and Pankaj K. Agarwal. Davenport-Schinzel sequences and their geometric applications. Cambridge University Press, 1995. Google Scholar
  16. Micha Sharir and Hayim Shaul. Semialgebraic range reporting and emptiness searching with applications. SIAM J. Comput., 40(4):1045-1074, 2011. URL: https://doi.org/10.1137/090765092.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact