Range searching

The range searching problems and data structures are a fundamental topic of computational geometry. The range searching problem finds applications not only in areas that deal with processing geometrical data (like geographical information systems (GIS), and CAD), but also in databases.

In its most general form, the problem consists of preprocessing a set S of objects, in order to determine which objects from S a query object, called a range, intersects. For example, S may be a set of points corresponding to the coordinates of several cities, and we want to find the cities within a certain latitude and longitude range.

Variations

There are several variations of the problem, and different data structures may be necessary for different variations. In order to obtain an efficient solution, several aspects of the problem need to be specified:

Object types: It is important to know whether S contains points, lines, line segments, polygons... The easiest and most studied sets of objects contain only points.

Range types: The query ranges also need to be drawn from a predetermined set. Some well-studied sets of ranges, and the names of the respective problems are axis-aligned rectangles (orthogonal range searching), simplices (simplex range searching), halfspaces (halfspace range searching), and spheres (spherical range searching). Orthogonal range queries can be answered much more efficiently than queries with all other range types mentioned above.

Query types: If the list of all objects that intersect the query range must be reported, the problem is called range reporting, and the query is called a reporting query. Sometimes, only the number of objects that intersect the range is required. In this case, the problem is called range counting, and the query is called a counting query. The emptiness query reports whether there is at least one object that intersects the range. In the semigroup version, a commutative semigroup (S,+) is specified, each point is assigned a weight from S, and it is required to report the semigroup sum of the weights of the points that intersect the range.

References

de Berg, van Kreveld, Overmars, Schwarzkopf. Computational Geometry, 2nd Edition. Berlin: Springer, 2000. ch. 5 and 16. ISBN 3-540-65620-0
J. Matoušek. Geometric range searching. ACM Computing Surveys, 26(4):421-461, 1994.
Pankaj K. Agarwal, and Jeff Erickson. Geometric range searching and its relatives. In Bernard Chazelle, Jacob Goodman, and Richard Pollack, editors,Advances in Discrete and Computational Geometry, pages 1-56. American Mathematical Society, 1998.