A Survey of Techniques for Fixed Radius Near Neighbor Searching
Jon Louis Bentley, USDOE Office of Science (SC) · 1975
This paper is a survey of techniques used for searching in a multidimensional space. Though we consider specifically the problem of searching for fixed radius near neighbors (that is, all points within a fixed distance of a given point), the structures presented here are applicable to many different search problems in multidimensional spaces. The orientation of this paper is practical; no theoretical results are presented. Many areas open for further research are mentioned.