Ray Shooting and Parametric Search

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