RAY SHOOTING AND PARAMETRIC SEARCH

Efficient algorithms for the ray shooting problem are presented: Given a collection GAMMA of objects in R(d), build a data structure so that, for a query ray, the first object of GAMMA 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 less-than-or-equal-to m less-than-or-equal-to n(b)) the queries are answered in time O((n/m1/b) log(O(1))n), with O(m1+epsilon) space and preprocessing time (epsilon > 0 is arbitrarily small but fixed constant). b = right perpendicular d/2 left perpendicular 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 R(d), and b = 3 for an arrangement of n half planes in R3. 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(m1+epsilon/n) per insert/delete operation.