A well-separated pairs decomposition algorithm for k-d trees implemented on multi-core architectures
Raul Lopes, Ivan D. Reid, P. R. Hobson · Journal of Physics Conference Series · 2014
Variations of k-d trees represent a fundamental data structure used in Computational Geometry with numerous applications in science. For example particle track fitting in the software of the LHC experiments, and in simulations of N-body systems in the study of dynamics of interacting galaxies, particle beam physics, and molecular dynamics in biochemistry. The many-body tree methods devised by Barnes and Hutt in the 1980s and the Fast Multipole Method introduced in 1987 by Greengard and Rokhlin use variants of k-d trees to reduce the computation time upper bounds to O ( n log n ) and even O ( n ) from O ( n 2 ). We present an algorithm that uses the principle of well-separated pairs decomposition to always produce compressed trees in O ( n log n ) work. We present and evaluate parallel implementations for the algorithm that can take advantage of multi-core architectures.