Document Open Access Logo

Line Intersection Searching Amid Unit Balls in 3-Space

Authors Pankaj K. Agarwal , Esther Ezra

PDF
Thumbnail PDF

File

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

Document Identifiers

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.

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

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.

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

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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