A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
Paul B. Callahan, S. Rao Kosaraju · Journal of the ACM · 1995
We define the notion of a well-separated pair decomposition of points in d -dimensional space. We then develop efficient sequential and parallel algorithms for computing such a decomposition. We apply the resulting decomposition to the efficient computation of k -nearest neighbors and n -body potential fields.