A decomposition of multi-dimensional point-sets with applications to <i>k</i>-nearest-neighbors and <i>n</i>-body potential fields (preliminary version)

Paul B. Callahan, S. Rao Kosaraju

1992 · 45 citations · 16 references

Concepts

Abstract

We define the notion of a well-separated pair decomposition of points in d-dimensional space. We 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.

References

16