Math @ Duke

Publications [#235392] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Matousek, J, On range searching with semialgebraic sets,
Discrete & Computational Geometry, vol. 11 no. 1
(1994),
pp. 393418, ISSN 01795376 [doi]
(last updated on 2018/06/20)
Abstract: Let P be a set of n points in ℝ d (where d is a small fixed positive integer), and let Γ be a collection of subsets of ℝ d, each of which is defined by a constant number of bounded degree polynomial inequalities. We consider the following Γrange searching problem: Given P, build a data structure for efficient answering of queries of the form, "Given a γ∈Γ, count (or report) the points of P lying in γ." Generalizing the simplex range searching techniques, we give a solution with nearly linear space and preprocessing time and with O(n 11/b+δ ) query time, where d≤b≤2d3 and δ>0 is an arbitrarily small constant. The acutal value of b is related to the problem of partitioning arrangements of algebraic surfaces into cells with a constant description complexity. We present some of the applications of Γrange searching problem, including improved ray shooting among triangles in ℝ3. © 1994 SpringerVerlag New York Inc.


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

