ABSTRACT
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 }^d $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315119601/fb8178cb-c53c-4311-b072-eff5ec016aba/content/inline-math40_1.tif"/> , and let R $ { \mathsf R } $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315119601/fb8178cb-c53c-4311-b072-eff5ec016aba/content/inline-math40_2.tif"/> be a family of subsets of R d $ { \mathbb R }^d $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315119601/fb8178cb-c53c-4311-b072-eff5ec016aba/content/inline-math40_3.tif"/> ; elements of R $ { \mathsf R } $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315119601/fb8178cb-c53c-4311-b072-eff5ec016aba/content/inline-math40_4.tif"/> 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 } $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315119601/fb8178cb-c53c-4311-b072-eff5ec016aba/content/inline-math40_5.tif"/> , the points in S ∩ γ $ S \cap \gamma $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315119601/fb8178cb-c53c-4311-b072-eff5ec016aba/content/inline-math40_6.tif"/> 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.
