I have a system of particles with equal distance with each other and another at random positions which is moving with time. I want to know:

a) The method by which I can reduce the number of particles from the first system, as I know the maximum motion of any particle is X.

b) How to efficiently calculate the collision between them, I have heard about quadtree and octree but (as per I understood till now) they are for collision of particle from each other. In my problem,second system of particles doesn't collide with each other.

Note: Sorry, if it is a very basic question, I am (very) new to this field.

  • $\begingroup$ What do you mean by 'maximum motion of any particle is X'? Do you mean maximum displacement? $\endgroup$
    – AlexE
    Commented Jun 27, 2014 at 11:55
  • $\begingroup$ Yes, actually I want to reduce the number of particles to reduce the calculation time. $\endgroup$ Commented Jun 27, 2014 at 11:57
  • $\begingroup$ Then I guess FMM-style methods using quadtrees in the plane or octrees in 3d or the way to go. Unfortunately, I can't point you to a specific reference or resource. $\endgroup$
    – AlexE
    Commented Jun 27, 2014 at 12:06

1 Answer 1


I would suggest Barnes-Hut type methods for this problem. It seems to fit the agenda perfectly and has a nice $\mathcal O(N\log N)$ complexity. You will have to augment it with your restrictions and conditions.

Barnes-Hut is a member of FMM-family, but it is much simpler than others and still covers your needs as far as I can see.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.