Math @ Duke
|
Publications [#235574] of Pankaj K. Agarwal
Papers Published
- Agarwal, PK; Matousek, J, Ray shooting and parametric search,
Siam Journal on Computing, vol. 22 no. 4
(January, 1993),
pp. 794-806, Society for Industrial & Applied Mathematics (SIAM) [doi]
(last updated on 2023/06/02)
Abstract: Efficient algorithms for the ray shooting problem are presented: Given a collection Γ of objects in Rd, build a data structure so that, for a query ray, the first object of Γ 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≤m≤nb) the queries are answered in time O((n/m1/b)logO(1)n), with O(m1+ε) space and preprocessing time (ε>0 is arbitrarily small but fixed constant). b = [d/2] 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 Rd, and b = 3 for an arrangement of n half planes in R3. 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(m1+ε/n) per insert/delete operation.
|
|
dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
| |
Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320
|
|