# Range searching

Published

Book Section

© 2018 by Taylor & Francis Group, LLC. 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.

• Agarwal, PK

### Published Date

• January 1, 2017

### Book Title

• Handbook of Discrete and Computational Geometry, Third Edition

• 1057 - 1092

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

• 9781498711395

### Digital Object Identifier (DOI)

• 10.1201/9781315119601

• Scopus