# Range searching

Book Section

A central problem in computational geometry, range searching arises in many applications, and a variety of geometric problems can be formulated as range-searching problems. A typical range-searching problem has the following form. Let S be a set of n points in R d $ { \mathbb R } $, and let R $ { \mathsf R } $ be a family of subsets of R d $ { \mathbb R } $ ; elements of R $ { \mathsf R } $ are called ranges. Typical examples of ranges include rectangles, halfspaces, simplices, and balls. Preprocess S into a data structure so that for a query range γ ε R $ \gamma \in { \mathsf R } $, the points in S ∩ γ $ S \cap \gamma $ can be reported or counted efficiently. A single query can be answered in linear time using linear space, by simply checking for each point of S whether it lies in the query range. Most of the applications, however, call for querying the same set S numerous times, in which case it is desirable to answer a query faster by preprocessing S into a data structure.

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK

### Published Date

- January 1, 2017

### Book Title

- Handbook of Discrete and Computational Geometry, Third Edition

### Start / End Page

- 1057 - 1092

### International Standard Book Number 13 (ISBN-13)

- 9781498711395

### Digital Object Identifier (DOI)

- 10.1201/9781315119601

### Citation Source

- Scopus