In
computational geometry, the
fixed-radius near neighbor problem is a variant of the
nearest neighbor search problem. In the fixed-radius near neighbor problem, one is given as input a set of points in
d-dimensional
Euclidean space and a fixed distance Δ. One must design a data structure that, given a query point
q, efficiently reports the points of the data structure that are within distance Δ of
q. The problem has long been studied; cites a 1966 paper by Levinthal that uses this technique as part of a system for visualizing molecular structures, and it has many other applications.