Two Dimensional Range Query

Find all points in the plane, given bounds in x and/or y.

I know that the solution for bounds given in x AND y is hard, but efficient solutions exist for x OR y, or even xmin < x < xmax AND ymin < y.

Can somebody add some references?

-- Gunnar Zarncke

Some solutions are quadtrees, k-d trees and R- and R*-trees. If you go back to the seminal papers, and trace the citations, you'll find a wealth of literature, including several entire textbooks, on the subject of orthogonal range query.

Quad trees:

The seminal paper is Raphael A. Finkel and Jon Louis Bentley. "Quad trees: A data structure for retrieval on composite keys." Acta Informatica, 4:1--9, 1974. Unfortunately, I know of this one only in a "dead trees" version, but you can find its citation index at http://citeseer.ist.psu.edu/context/15748/0

k-d trees:

One classic paper in the field is Jon Bentley's "Multidimensional binary search trees used for associative searching." CACM 18:9 (September, 1975), pp. 509-517, available (by subscription) at http://doi.acm.org/10.1145/361002.361007

R-trees:

The key paper is Antonin Guttman, "R-trees: a dynamic index structure for spatial searching." ACM SIGMOD Record 14:2 (1984), pp. 47-57. http://doi.acm.org/10.1145/971697.602266

CategoryAlgorithm