ON RANGE SEARCHING WITH SEMIALGEBRAIC SETS

Let P be a set of n points in R(d) (where d is a small fixed positive integer), and let GAMMA be a collection of subsets of R(d), each of which is defined by a constant number of bounded degree polynomial inequalities. We consider the following GAMMA-range searching problem: Given P, build a data structure for efficient answering of queries of the form, ''Given a gamma is-an-element-of GAMMA, count (or report) the points of P lying in gamma.'' Generalizing the simplex range searching techniques, we give a solution with nearly linear space and preprocessing time and with O(n1-1/b+delta ) query time, where d less-than-or-equal-to b less-than-or-equal-to 2d - 3 and delta > 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 GAMMA-range searching problem, including improved ray shooting among triangles in R3.