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