Range Searching

Range searching is one of the central problems in computational geometry, because it arises in many applications and a wide variety of geometric problems be formulated as a range searching-problem. A typical range searching-problem has the following form. Let S be a set of n points in Rd, and let R be a family of subsets; elements of R are called ranges. We wish to process S into a data structure so that for a query range R, the points in S ∩ R can be reported or counted efficiently. Typical examples of ranges includes rectangles, halfspaces, simplices, and balls. If we are interested in answering a single query, it can be done in linear time, using linear space, by simply checking for each point p ∈ S whether p lies in the query range. However, most of the applications call for querying the same point set S several times ( or sometimes we also insert or delete a point periodically), in which case we would like to answer a query faster by processing S into a data structure