Ray Shooting and Parametric Search

Abstract

Efficient algorithms for the ray shooting problem are presented: Given a collection $\Gamma $ of objects in $\mathbb{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 \leqslant m \leqslant n^b )$ the queries are answered in time $O(({n / {m^{{1 / b}} }})\log ^{O(1)} n)$, with $O(m^{1 + \varepsilon } )$ space and preprocessing time ($\varepsilon > 0$ is arbitrarily small but fixed constant). $b = \lfloor {{d / 2}} \rfloor $ 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 $\mathbb{R}^d $, and $b = 3$ for an arrangement of n half planes in $\mathbb{R}^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^{1 + \varepsilon } } / n})$ per insert/delete operation.