Math @ Duke

Publications [#235566] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Matousek, J, Ray shooting and parametric search,
in Twenty Fourth Annual ACM Symposium on Theory of Computing,
Conference Proceedings of the Annual ACM Symposium on Theory of Computing
(1992),
pp. 517526
(last updated on 2018/05/25)
Abstract: We present efficient algorithms for the ray shooting problem: Given a collection Γ of objects in Rd, build a data structure, so that one can quickly determine the first object of Γ 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/b logO(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 dpolytope defined as an intersection of n halfspaces, b = d for an arrangement of n hyperplanes in Rd and b = 3 for an arrangement of n halfplanes in R3. Next we apply the ray shooting algorithms to several problems including reporting knearest (or kfarthest) neighbors, hidden surface removal, computing convex layers, and computing levels in arrangements of planes. All the algorithms described here either give the first nontrivial solutions to these problems, or improve the previously best known solutions significantly.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

