n objects in d, build a data structure so that, for a query ray p, we can quickly determine the first object ofF intersected by p. The ray shooting problem has received much attention in the past few years because of its
Ray Shooting, Pankaj K. Agarwal Ano · 1993
Efficient algorithms for the ray shooting problem are presented: Given a collection F of objects in d, build a data structure so that, for a query ray, the first object of F hit by the ray can be quickly determined. Using the parametric search technique, this problem is reduced to the segment emptiness problem. For various ray shooting problems, space/query-time trade-offs of the following type are achieved: For some integer b and a parameter m (n _ 0 is arbitrarily small but fixed constant), b Ld/2J is obtained for ray shooting in a convex d-polytope defined as an intersection of n half spaces, b d for an arrangement of n hyperplanes in d, and b 3 for an arrangement of n half planes in 3. This approach also yields fast procedures for finding the first k objects hit by a query ray, for searching nearest and farthest neighbors, and for the hidden surface removal. All the data structures can be maintained dynamically in amortized time O(m + /n) per insert/delete operation.