Truly distribution-independent algorithms for the N-body problem

The N-body problem is to simulate the motion of N particles under the influence of mutual force fields based on an inverse square law. Greengard´s algorithm claims to compute the cumulative force on each particle in O(N) time for a fixed precision irrespective of the distribution of the particles. In this paper, we show that Greengard´s algorithm is distribution dependent and has a lower bound of Ω(N log² N) in two dimensions and Ω(N log⁴ N) in three dimensions. We analyze the Greengard and Barnes-Hut algorithms and show that they are unbounded for arbitrary distributions. We also present a truly distribution independent algorithm for solving the N-body problem in O(N log N) time in two dimensions and in O(N log² N) time in three dimensions