Range Searching

Authored by: Pankaj K. Agarwal

Discrete and Computational Geometry

Print publication date:  April  2004
Online publication date:  April  2004

Print ISBN: 9781584883012
eBook ISBN: 9781420035315
Adobe ISBN:

10.1201/9781420035315.ch36

 Download Chapter

 

Abstract

Range searching is one of the central problems in computational geometry, because it 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 ? d , and let R be a family of subsets of ? d ; elements of R are called ranges . We wish to preprocess S into a data structure, so that for a query range ?, the points in S ∩ ? can be reported or counted efficiently. Typical examples of ranges include rectangles, halfspaces, simplices, and balls. If we are only interested in answering a single query, it can be done in linear time, using linear space, by simply checking each point of S whether it lies in the query range. However, most of the applications call for querying the same set S several times (perhaps with periodic insertions and deletions), in which case we would like to answer a query faster by preprocessing S into a data structure.

 Cite
Search for more...
Back to top

Use of cookies on this website

We are using cookies to provide statistics that help us give you the best experience of our site. You can find out more in our Privacy Policy. By continuing to use the site you are agreeing to our use of cookies.