1992 · 45 citations · 16 references
ComputingComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingDimensionality ReductionNearest Neighbor SearchParallel Computational GeometryK-nearest NeighborsParallel Reduction Algorithms
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.
16
A fast algorithm for particle simulations
Leslie Greengard, Vladimir Rokhlin · Journal of Computational Physics · 1987 · 4.9K citations
A hierarchical O(N log N) force-calculation algorithm
Josh Barnes, Piet Hut · Nature · 1986 · 3.7K citations
Computational geometry. an introduction
Franco P. Preparata, Michael Ian Shamos · 1985 · 2.4K citations
Multidimensional divide-and-conquer
Jon Bentley · Communications of the ACM · 1980 · 676 citations · Full text