Ray shooting and parametric search

Published

Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Matoušek, J

Published Date

  • July 1, 1992

Published In

Volume / Issue

  • Part F129722 /

Start / End Page

  • 517 - 526

International Standard Serial Number (ISSN)

  • 0737-8017

Digital Object Identifier (DOI)

  • 10.1145/129712.129763

Citation Source

  • Scopus