Approximate range searching☆☆A preliminary version of this paper appeared in the Proc. of the 11th Annual ACM Symp. on Computational Geometry, 1995, pp. 172–181.

Arya, 1998, An optimal algorithm for approximate nearest neighbor searching, Journal of the ACM, 45, 891, 10.1145/293347.293348

Bentley, 1990, K-d trees for semidynamic point sets, 187

Bern, 1993, Approximate closest-point queries in high dimensions, Inform. Process. Lett., 45, 95, 10.1016/0020-0190(93)90222-U

Brönnimann, 1993, How hard is halfspace range searching, Discrete Comput. Geom., 10, 143, 10.1007/BF02573971

Callahan, 1995, A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields, Journal of the ACM, 42, 67, 10.1145/200836.200853

Chazelle, 1989, Lower bounds on the complexity of polytope range searching, J. Amer. Math. Soc., 2, 637, 10.1090/S0894-0347-1989-1001852-0

Chazelle, 1989, Quasi-optimal range searching in spaces of finite VC-dimension, Discrete Comput. Geom., 4, 467, 10.1007/BF02187743

Clarkson, 1983, Fast algorithms for the all nearest neighbors problem, 226

Duncan, 1999, Balanced aspect ratio trees: Combining the advantages of k–d trees and octrees

Farvardin, 1985, Rate-distortion performance of DPCM schemes for autoregressive sources, IEEE Trans. Inform. Theory, 31, 402, 10.1109/TIT.1985.1057040

Matous̆ek, 1993, Range searching with efficient hierarchical cuttings, Discrete Comput. Geom., 10, 157, 10.1007/BF02573972

Overmars, 1992, Point location in fat subdivisions, Inform. Process. Lett., 44, 261, 10.1016/0020-0190(92)90211-D

Preparata, 1985

Samet, 1990

Vaidya, 1989, An O(nlogn) algorithm for the all-nearest-neighbors problem, Discrete Comput. Geom., 4, 101, 10.1007/BF02187718

Willard, 1982, Polygon retrieval, SIAM J. Comput., 11, 149, 10.1137/0211012