# Particle Collision to Static paticles

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.

• What do you mean by 'maximum motion of any particle is X'? Do you mean maximum displacement? – AlexE Jun 27 '14 at 11:55
• Yes, actually I want to reduce the number of particles to reduce the calculation time. – Devashish Das Jun 27 '14 at 11:57
• 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. – AlexE Jun 27 '14 at 12:06

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.