# On range searching with semialgebraic sets

Journal Article

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 1-1/b+δ ) query time, where d≤b≤2d-3 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 Springer-Verlag New York Inc.

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK; Matousek, J

### Published Date

- December 1, 1994

### Published In

### Volume / Issue

- 11 / 1

### Start / End Page

- 393 - 418

### Electronic International Standard Serial Number (EISSN)

- 1432-0444

### International Standard Serial Number (ISSN)

- 0179-5376

### Digital Object Identifier (DOI)

- 10.1007/BF02574015

### Citation Source

- Scopus