In this paper, we study data structures for use in N-body simulation. We co
ncentrate on the spatial decomposition tree used in particle-cluster force
evaluation algorithms such as the Barnes-Hut algorithm. We prove that a k-d
tree is asymptotically inferior to a spatially balanced tree. We show that
the worst case complexity of the force evaluation algorithm using a k-d tr
ee is Theta(n log(3) n log L) compared with Theta(n log L) for an oct-tree.
(L is the separation ratio of the set of points.)
We also investigate improving the constant factor of the algorithm and pres
ent several methods which improve over the standard oct-tree decomposition.
Finally, we consider whether or not the bounding box of a point set should
be "tight" and show that it is safe to use tight bounding boxes only for b
inary decompositions. The results are all directly applicable to practical
implementations of N-body algorithms.