The complexity of finding fixed-radius near neighbors (Q1244819)

Given a finite set \(S\) of \(N\) points in \(k\)-space, and a positive radius \(\delta\), the ``fixed-radius near neighbors problem'' calls for finding all pairs of points which are within the specified distance \(\delta\) of one another. This problem arises in such applications as molecular graphics, density estimation, and cluster analysis. In this paper we present and analyze algorithms for solving the fixed-radius near neighbors problem when the distances between points are measured by the \(_\infty\), or ``maximum coordinate'', metric. The number of fixed radius near neighbor pairs in a point set can vary between zero and \(N\cdot(N-1)/2\). Any algorithm which correctly finds all near neighbors must therefore take at least \(O(N^2)\) time in the worst case, if the complexity is measured only as a function of the input size \(N\). In this paper we present an algorithm and measure its complexity as a function of \(N\) (the input size) and \(F\) (the number of points found, or the output size). We show that all \(F\) near neighbors can be found in \(O(N\log N+F)\) time on a RAM/RASP machine using only linear storage. The analysis of the algorithm is unusual in that the complexity is measured as a function of both input and output sizes, where the output size is unknown beforehand.