# 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