Ray shooting and parametric search
We present efficient algorithms for the ray shooting problem: Given a collection γ of objects in ℝd, build a data structure, so that one can quickly determine the first object of T hit by a query ray. Using the parametric search technique, we reduce this problem to the segment emptiness problem. For various ray shooting problems, we achieve space/query time tradeoffs of the following type: for some integer b and a parameter m (n ≤ m ≤ nb) the queries are answered in time O(n/m1/blogo(1)n), with O(m1+ϵ) space and preprocessing time (ϵ > 0 is arbitrarily small but fixed). We get b = [d/2\ 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 ℝd and b = 3 for an arrangement of n half-planes in ℝ3. Next we apply the ray shooting algorithms to several problems including reporting fc-nearest (or fc-farthest) neighbors, hidden surface removal, computing convex layers, and computing levels in arrangements of planes. All the algorithms described here either give the first non-trivial solutions to these problems, or improve the previously best known solutions significantly.
Volume / Issue
Start / End Page
International Standard Serial Number (ISSN)
Digital Object Identifier (DOI)