נתן רובין

We consider the problem of ray shooting in a three-dimensional scene consisting of k (possibly intersecting) convex polyhedra with a total of n facets. That is, we want to preprocess them into a data structure, so that the first intersection point of a query ray and the given polyhedra can be determined quickly. We describe data structures that require Õ(npoly(k)) preprocessing time and storage, and have polylogarithmic query time, for several special instances of the problem. These include the case when the ray origins are restricted to lie on a fixed line ℓ₀, but the directions of the rays are arbitrary, the more general case when the supporting lines of the rays pass through ℓ₀, and the case of rays orthogonal to z-axis with arbitrary origins. In all cases, this is a significant improvement over previously known techniques (which require Ω(n²) storage, even when A: ≪ n).