Document Open Access Logo

On Ray Shooting for Triangles in 3-Space and Related Problems

Authors Esther Ezra , Micha Sharir

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.34.pdf
  • Filesize: 0.76 MB
  • 15 pages

Document Identifiers

Author Details

Esther Ezra
  • School of Computer Science, Bar Ilan University, Ramat Gan, Israel
Micha Sharir
  • School of Computer Science, Tel Aviv University, Israel

Funding

  • Ezra, Esther: Work partially supported by NSF CAREER under grant CCF:AF-1553354 and by Grant 824/17 from the Israel Science Foundation.
  • Sharir, Micha: Work partially supported by ISF Grant 260/18, by grant 1367/2016 from the German-Israeli Science Foundation (GIF), and by Blavatnik Research Fund in Computer Science at Tel Aviv University.

Acknowledgements

We wish to thank Pankaj Agarwal for the useful interaction concerning certain aspects of the range searching problem.

Cite As Get BibTex

Esther Ezra and Micha Sharir. On Ray Shooting for Triangles in 3-Space and Related Problems. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.SoCG.2021.34

Abstract

We consider several problems that involve lines in three dimensions, and present improved algorithms for solving them. The problems include (i) ray shooting amid triangles in ℝ³, (ii) reporting intersections between query lines (segments, or rays) and input triangles, as well as approximately counting the number of such intersections, (iii) computing the intersection of two nonconvex polyhedra, (iv) detecting, counting, or reporting intersections in a set of lines in ℝ³, and (v) output-sensitive construction of an arrangement of triangles in three dimensions.
Our approach is based on the polynomial partitioning technique.
For example, our ray-shooting algorithm processes a set of n triangles in ℝ³ into a data structure for answering ray shooting queries amid the given triangles, which uses O(n^{3/2+ε}) storage and preprocessing, and answers a query in O(n^{1/2+ε}) time, for any ε > 0. This is a significant improvement over known results, obtained more than 25 years ago, in which, with this amount of storage, the query time bound is roughly n^{5/8}. The algorithms for the other problems have similar performance bounds, with similar improvements over previous results. 
We also derive a nontrivial improved tradeoff between storage and query time. Using it, we obtain algorithms that answer m queries on n objects in max{O(m^{2/3}n^{5/6+{ε}} + n^{1+ε}), O(m^{5/6+ε}n^{2/3} + m^{1+ε})} time, for any ε > 0, again an improvement over the earlier bounds.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Ray shooting
  • Three dimensions
  • Polynomial partitioning
  • Tradeoff

Metrics

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

Related Versions

References

  1. P. K. Agarwal. Simplex range searching and its variants: A review. In J. Nešetřil M. Loebl and R. Thomas, editors, Journey through Discrete Mathematics: A Tribute to Jiří Matoušek, pages 1-30. Springer Verlag, Berlin-Heidelberg, 2017. Google Scholar
  2. P. K. Agarwal, B. Aronov, E. Ezra, and J. Zahl. An efficient algorithm for generalized polynomial partitioning and its applications. In Proc. Internat. Sympos. on Computational Geometry, pages 5:1-5:14, 2019. Also in URL: https://arxiv.org/abs/1812.10269.
  3. P. K. Agarwal and J. Matoušek. Ray shooting and parameric search. SIAM J. Comput., 22:794-806, 1993. Google Scholar
  4. P. K. Agarwal and M. Sharir. Ray shooting amidst convex polyhedra and polyhedral terrains in three dimensions. SIAM J. Comput., 25:100-116, 1996. Google Scholar
  5. P. K. Agarwal, M. van Kreveld, and M. Overmars. Intersection queries in curved objects. J. Algorithms, 15:229-266, 1993. Google Scholar
  6. B. Aronov, E. Ezra, and J. Zahl. Constructive polynomial partitioning for algebraic curves in R³ with applications. SIAM J. Comput., 49:1109-1127, 2020. Also in Proc. Sympos. on Discrete Algorithms (SODA), 2019, 2636-2648. Also in URL: https://arxiv.org/abs/1904.09526.
  7. S. Basu, R. Pollack, and M.-F. Roy. Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics 10. Springer-Verlag, Berlin, 2003. Google Scholar
  8. O. Bottema and B. Roth. Theoretical Kinematics. Dover, New York, 1990. Google Scholar
  9. B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. A singly exponential stratification scheme for real semi-algebraic varieties and its applications. Theoretical Computer Science, 84:77-105, 1991. Google Scholar
  10. B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. Algorithms for bichromatic line segment problems and polyhedral terrains. Algorithmica, 11:116-132, 1994. Google Scholar
  11. B. Chazelle, H. Edelsbrunner, L. J. Guibas, M. Sharir, and J. Stolfi. Lines in space: Combinatorics and algorithms. Algorithmica, 15:428-447, 1996. Google Scholar
  12. G. E. Collins. Quantifier elimination for the elementary theory of real closed fields by cylindrical algebraic decomposition. In Proc. 2nd GI Conf. Automata Theory and Formal Languages. Springer LNCS 33, 1975. Google Scholar
  13. M. de Berg. Ray Shooting, Depth Orders and Hidden Surface Removal. Lecture Notes Comput. Sci., 703. Springer Verlag, Berlin, 1993. Google Scholar
  14. M. de Berg, D. Halperin, M. Overmars, J. Snoeyink, and M. van Kreveld. Efficient ray shooting and hidden surface removal. Algorithmica, 12:30-53, 1994. Google Scholar
  15. E. Ezra and M. Sharir. On ray shooting for triangles in 3-space and related problems. URL: http://arxiv.org/abs/2102.07310.
  16. L. Guth. Polynomial partitioning for a set of varieties. Math. Proc. Camb. Phil. Soc., 159:459-469, 2015. Also in URL: https://arxiv.org/abs/1410.8871.
  17. L. Guth and N.~H. Katz. On the erdH os distinct distances problem in the plane. Annals Math., 181:155-190, 2015. Also in URL: https://arxiv.org/abs/1011.4105.
  18. C. G. A. Harnack. Über die vielfaltigkeit der ebenen algebraischen kurven. Math. Ann., 10:189-199, 1876. Google Scholar
  19. K. Hunt. Kinematic Geometry of Mechanisms. Oxford, 1990. Google Scholar
  20. V. Koltun. Segment intersection searching problems in general settings. Discrete Comput. Geom., 30:25-44, 2003. Google Scholar
  21. J. Matoušek and O. Schwarzkopf. On ray shooting in convex polytopes. Discrete Comput. Geom., 10:215-232, 1993. Google Scholar
  22. M. McKenna and J. O'Rourke. Arrangements of lines in 3-space: A data structure with applications. In Proc. 4th ACM Sympos. Computational Geometry, pages 371-380, 1988. Google Scholar
  23. M. Pellegrini. Ray shooting on triangles in 3-space. Algorithmica, 9:471-494, 1993. Google Scholar
  24. M. Pellegrini. Ray shooting and lines in space. In J. O'Rourke J. E. Goodman and C. D. Tóth, editors, Handbook on Discrete and Computational Geometry, chapter 41, pages 1093-1112. CRC Press, Boca Raton, Florida, Third Edition, 2017. Google Scholar
  25. J.T. Schwartz and M. Sharir. On the piano movers' problem: Ii. general techniques for computing topological properties of real algebraic manifolds. Advances in Appl. Math., 4:298-351, 1983. Google Scholar
  26. J. Stolfi. Oriented Projective Geometry. Academic Press, New York, 1991. Google Scholar
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