Range searching

Simplex range searching.

In its most general form, the range searching problem consists of preprocessing a set S of objects, in order to determine which objects from S intersect with a query object, called a range. 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.

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.

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:

References

This article is issued from Wikipedia - version of the Monday, July 28, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.