Stony Brook Algorithm Repository


Range Search

Input
Output

Input Description: A set \(S\) of \(n\) points in \(E^d\), and a query polygon \(Q\).
Problem: Which points from \(S\) lie within \(Q\)?

Excerpt from The Algorithm Design Manual: Range search problems arise in database and geographic information system (GIS) applications. Any data object with \(d\) numerical fields, such as person with height, weight, and income, can be modeled as a point in \(d\)-dimensional space. A range query describes a region in space and asks for all points or the number of points in the region. For example, asking for all people with income between $0 and $10,000, with height between 6'0'' and 7'0'', and weight between 50 and 140 lbs. defines a box containing people whose body and wallets are both thin.


Implementations

annoy (rating 9)
pysparnn (rating 8)
nanoflann (rating 8)
flann (rating 8)
CGAL (rating 8)
LEDA (rating 8)
ANN (rating 7)
Ranger (rating 4)
Algorithms in C++ (rating 3)
Handbook of Algorithms and Data Structures (rating 2)


Recommended Books

Algorithms in Java, Third Edition (Parts 1-4) by Robert Sedgewick and Michael Schidlowsky Computational Geometry : Algorithms and Applications by Mark De Berg, Marc Van Kreveld, Mark Overmars, and O. Schwartskopf Computational Geometry in C by Joseph O'Rourke
Handbook of Algorithms and Data Structures by G. Gonnet and R. Baeza-Yates Computational Geometry by F. Preparata and M. Shamos

Related Problems


Kd-Trees

Nearest Neighbor Search

Point Location

Go To Main Page