Personal tools
You are here: Home CG seminar 2021 On ray shooting amid triangles in three dimensions and related problems
« August 2021 »
August
SuMoTuWeThFrSa
1234567
891011121314
15161718192021
22232425262728
293031
Log in


Forgot your password?
 

On ray shooting amid triangles in three dimensions and related problems

Wednesday, December 30th, 16:10

underline

Esther Ezra, Bar Ilan University

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 three dimensions, (ii) reporting intersections between query lines (segments, or rays) and input triangles, (iii) computing the intersection of two nonconvex polyhedra, (iv) detecting, counting, or reporting intersections in a set of lines in 3-space, 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 R^3 into a data structure for answering ray shooting queries amid the given triangles, which uses O(n^{3/2+\eps}) storage and preprocessing, and answers a query in O(n^{1/2+\eps}) time, for any \eps > 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.  
 
Joint work with Micha Sharir.
 
Document Actions