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

Math @ Duke



Publications [#235572] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Sharir, M, Ray shooting amidst convex polytopes in three dimensions, Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (1993), pp. 260-270
    (last updated on 2018/10/19)

    We consider the problem of ray shooting in a 3-dimensional scene consisting of m (possibly intersecting) convex polyhedra with a total of n faces, i.e., we want to preprocess them into a data structure, so that the first intersection point of a query ray and the given polyhedra can be determined quickly. We present a technique that requires O((mn)2+ε) preprocessing time and storage, and can answer ray shooting queries in O(log n) time. This is a significant improvement over previously known techniques (which require O(n4+ε) space and preprocessing) if m is much smaller than n, which is often the case in practice. We also present a variant of the technique that requires O(n1+ε) space and preprocessing, and answers queries in time O(m1/4n1/2+ε), again a significant improvement over previous techniques when m≪n. Our algorithms also work when the given polyhedra intersect, and also apply to a collection of (possibly intersecting) polyhedral terrains.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320