In
computational geometry, the fixed-radius near neighbor problem is a variant of the
nearest neighbor search
Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest (or most similar) to a given point. Closeness is typically expressed in terms of a dissimilarity function: ...
problem. In the fixed-radius near neighbor problem, one is given as input a set of points in ''d''-dimensional
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...
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.
Solution by rounding and hashing
One method for solving the problem is to round the points to an
integer lattice
In mathematics, the -dimensional integer lattice (or cubic lattice), denoted , is the lattice (group), lattice in the Euclidean space whose lattice points are tuple, -tuples of integers. The two-dimensional integer lattice is also called the s ...
, scaled so that the distance between grid points is the desired distance Δ. A
hash table
In computer science, a hash table is a data structure that implements an associative array, also called a dictionary or simply map; an associative array is an abstract data type that maps Unique key, keys to Value (computer science), values. ...
can be used to find, for each input point, the other inputs that are mapped to nearby grid points, which can then be tested for whether their unrounded positions are actually within distance Δ. The number of pairs of points tested by this procedure, and the time for the procedure, is linear in the combined input and output size when the dimension is a fixed constant. However, the
constant of proportionality
In mathematics, two sequences of numbers, often experimental data, are proportional or directly proportional if their corresponding elements have a constant ratio. The ratio is called ''coefficient of proportionality'' (or ''proportionality c ...
in the linear time bound
grows exponentially
Exponential growth occurs when a quantity grows as an exponential function of time. The quantity grows at a rate directly proportional to its present size. For example, when it is 3 times as big as it is now, it will be growing 3 times as fast ...
as a function of the dimension. Using this method, it is possible to construct
indifference graph
In graph theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other.. Indifference ...
s and
unit disk graph
In geometric graph theory, a unit disk graph is the intersection graph of a family of unit disks in the Euclidean plane. That is, it is a graph with one vertex for each disk in the family, and with an edge between two vertices whenever the corres ...
s from geometric data in linear time.
Other solutions
Modern parallel methods for GPU are able to efficiently compute all pairs fixed-radius NNS. For finite domains, the method of Green shows the problem can be solved by sorting on a uniform grid, finding all neighbors of all particles in O(kn) time, where k is proportional to the average number of neighbors. Hoetzlein
improves this further on modern hardware with counting sorting and atomic operations.
Applications
The fixed-radius near neighbors problem arises in continuous Lagrangian simulations (such as smoothed particle hydrodynamics), computational geometry, and point cloud problems (surface reconstructions).
See also
*
Cell lists Cell lists (also sometimes referred to as cell linked-lists) is a data structure in molecular dynamics simulations to find all atom pairs within a given cut-off distance of each other. These pairs are needed to compute the short-range non-bonded int ...
References
{{reflist
Geometric algorithms