Barnes Hut worst case memory scenario

Question

I want to run a Barnes Hut N-body simulation (Wikipedia article). I know how much memory a single node of the octree will occupy, but I can't figure out what a worst case memory usage scenario would be for a given number of particles. In short, I'm wondering how many nodes could possibly exist in the octree for a given number of particles. I need to know this to know how much memory to allocate for the octree.

Edit:

Oh, and I'm writing in C if anybody wants to give me code instead of just and explanation.

I have this, which is way worse than a worst case scenario. But it's guaranteed to AT LEAST allocate enough memory. I'm hoping somebody can give me something a little more memory efficient.

int KBH_worstcase(int particles)
{ // returns number of nodes required to store a number of particles in a worst case scenario
    int worst;
    unsigned int n;
    worst=1;
    n=1;
    while(n<particles)
    {
        n=n<<3;
        worst+=n;
    }
    return worst;
}

Answer 1

I'm not sure if such a suitable criterion exists. The octree takes into account the particles distribution which is likely to change during the simulation. So the effective depth of the tree cannot rely only on the number of particles.

One spurious solution could be to define a bound on the tree depth (or on the number of nodes). In such a case you could group more particles in a single cell (the leaves of the octree) and fall back to the body-body interaction. But if you want more control on the tree structure, maybe is better to have the ability to allocate new nodes when necessary.

Answer 2

Actually, the upper limit of the number of nodes needed for the quad-tree (or octree for three dimensions) is not limited by the logarithm of the total number of particles.

Normally space in a node is divided in four equal quadrants. Consider a case where two particles are very close to each other compared to the bounding box of the root node. Here it is easy to see that a lots of internal nodes needs to be created before reaching nodes with a single particle. See sketch below.

Lots of internal nodes - Only two points

The upper bound in two dimensions should instead be (top of my head)

log4 w/m

Where w is the size of the bounding box of the root node and m is the shortest distance between any two particles.

However, computing the shortest distance between any two points has O(n^2) complexity which you'd want to avoid.

You can instead modify the algorithm to only build the tree to a maximum depth d. This will limit the memory consumption to 4^(d+1)−1 nodes.

You also need to handle the interactions withing nodes with more than one particles with care, e.g. falling back to the naive O(n^2) algorithm.