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

CategoryAlgorithm

EditText of this page (last edited May 30, 2006) or FindPage with title or text search