Range searching
In computer science, the range searching problem consists of processing a set S of objects, in order to determine which objects from S intersect with a query object, called the range.
The range searching problem and the data structures that solve it are a fundamental topic of computational geometry.
Applications of the problem arise in areas such as geographical information systems (GIS), computer-aided design (CAD) and databases.
[1] In order to obtain an efficient solution, several aspects of the problem need to be specified: In orthogonal range searching, the set S consists of
Thus, the query consists of a multi-dimensional axis-aligned rectangle.
, Jon Bentley used a k-d tree to achieve (in Big O notation)
[2] Bentley also proposed using range trees, which improved query time to
[3] Dan Willard used downpointers, a special case of fractional cascading to reduce the query time further to
[4] While the above results were achieved in the pointer machine model, further improvements have been made in the word RAM model of computation in low dimensions (2D, 3D, 4D).
Bernard Chazelle used compress range trees to achieve
[5] Joseph JaJa and others later improved this query time to
for range counting, which matches a lower bound and is thus asymptotically optimal.
[6] As of 2015, the best results (in low dimensions (2D, 3D, 4D)) for range reporting found by Timothy M. Chan, Kasper Larsen, and Mihai Pătrașcu, also using compressed range trees in the word RAM model of computation, are one of the following:[7] In the orthogonal case, if one of the bounds is infinity, the query is called three-sided.
While in static range searching the set S is known in advance, dynamic range searching, insertions and deletions of points are allowed.
For the orthogonal case, Kurt Mehlhorn and Stefan Näher created a data structure for dynamic range searching which uses dynamic fractional cascading to achieve
[8] Both incremental and decremental versions of the problem can be solved with
The problem of colored range counting considers the case where points have categorical attributes.
Prosenjit Gupta and others described a data structure in 1995 which solved 2D orthogonal colored range counting in
For example, determining the rows in a database of bank accounts which represent people whose age is between 25 and 40 and who have between $10000 and $20000 might be an orthogonal range reporting problem where age and money are two dimensions.
