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 qui ckly determined. Using the parametric search technique, this problem i s reduced to the segment emptiness problem. For various ray shooting p roblems, space/query-time trade-offs of the following type are achieve d: For some integer b and a parameter m (n less-than-or-equal-to m les s-than-or-equal-to n(b)) the queries are answered in time O((n/m1/b) l og(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-polyt ope defined as an intersection of n half spaces, b = d for an arrangem ent of n hyperplanes in R(d), and b = 3 for an arrangement of n half p lanes in R3. This approach also yields fast procedures for finding the first k objects hit by a query ray, for searching nearest and farthes t neighbors, and for the hidden surface removal. All the data structur es can be maintained dynamically in amortized time O(m1+epsilon/n) per insert/delete operation.