License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2021.34
URN: urn:nbn:de:0030-drops-138332
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13833/
Ezra, Esther ;
Sharir, Micha
On Ray Shooting for Triangles in 3-Space and Related Problems
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.
BibTeX - Entry
@InProceedings{ezra_et_al:LIPIcs.SoCG.2021.34,
author = {Ezra, Esther and Sharir, Micha},
title = {{On Ray Shooting for Triangles in 3-Space and Related Problems}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {34:1--34:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13833},
URN = {urn:nbn:de:0030-drops-138332},
doi = {10.4230/LIPIcs.SoCG.2021.34},
annote = {Keywords: Ray shooting, Three dimensions, Polynomial partitioning, Tradeoff}
}
|
Keywords: |
|
Ray shooting, Three dimensions, Polynomial partitioning, Tradeoff |
|
Collection: |
|
37th International Symposium on Computational Geometry (SoCG 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
02.06.2021 |
