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