Warp <war### [at] tagpovrayorg> wrote:
>   But you have to calculate the center of mass of the whole group, and
> since each element of the group can change independently of the others,
> that would mean you have to re-calculate this center of mass each time
> anything changes.

That is certainly the case, but even 100*(n log n) is still much smaller than
n^2 for large n.  And can't you just do this hierarchically anyway?  At each
step calculate the tree structure, calculate the center of masses
hierarchically, sum forces, and integrate?  Those steps all sound like O(n log
n), but that's still pretty good.  Of course you'd update everything together
so you wouldn't have to recalculate more than once per time step.

>   Also another problem is that groups don't stay the same. If a particle
> not belonging to the group enters the "inside" of the group, it cannot
> be calculated anymore against that group as if it was just one single
> mass located at the center of mass of the group.

That is very true, so you'd have to recalculate the tree for each step.  Even if
it's slightly outside though, the center of mass approximation is not exact.  I
guess the fast multipole method takes this a step further and you can get the
correct answer down to machine precision, but that's beyond me.

This page has a pretty good introduction:

http://www.cs.berkeley.edu/~demmel/cs267/lecture26/lecture26.html

 - Ricky

Post a reply to this message