Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#235566] of Pankaj K. Agarwal

Papers Published

  1. 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. 517-526
    (last updated on 2017/12/13)

    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 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. Next we apply the ray shooting algorithms to several problems including reporting k-nearest (or k-farthest) 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 27708-0320