What is the formal name of the data-structure/algorithm for particle simulations presented here? -

for computer simulate system of n particles in universe interact each other, 1 use rough algorithm:

for interval dt=10ms   each particle in universe     each particle b in universe       interact(a,b,dt)   each particle in universe     integrate(a,dt) 

it heavy, calling interact n^2 times per tick - thus, unfeasible simulate many particles. of time, though, particles near interact less strongly. idea take advantage of fact, creating graph each node particle , each connection distance. particles near interact more particles far. example,

for interval dt=10ms   each particle in universe     each particle b 0m <= distance < 10m       interact(a,b,dt) interval dt=20ms   each particle in universe     each particle b 10m <= distance < 20m       interact(a,b,dt) interval dt=40ms   fro each particle in universe     each particle in b 20m <= distance < 40m       interact(a,b,dt) (...etc) interval dt=10ms   each particle in universe     integrate(a,dt)    

this superior, particle interact near. when particle far gets closer, start refreshing more frequently.

i need know math behind this, in order calculate optimal refresh rate between 2 particles in function of distance. thus, question is, formal name of describing here?

to overcome o(n^2) cost of calculating full set of pair-wise interactions @ each step, n-body simulations of kind implemented using barnes-hut approach. similar in spirit type of multi-resolution idea you've described.

barnes-hut efficient (o(n*log(n))) approximation full pair-wise interaction terms based on hierarchical spatial partitioning strategy. set of particles inserted octree (quadtree in r^2), spatial indexing tree height o(log(n)). in addition containing pointers children, nodes @ each level of tree contain center of mass of set of child particles - tree nodes in effect lumped "super-particles" @ various spatial resolutions.

when calculating force acting on particular particle tree traversed root, , @ each node decision made whether continue traversing it's children, or take approximate 'lumped' contribution based on center of mass of children. typically, decision made based on distance of center of mass particle in question - if center of mass "far enough away" traversal terminates , "lumped" approximation taken.

this strategy ensures full (and expensive) pair-wise interaction computed @ "short" particle distances, approximate "lumped" interactions used distance increases.

state-of-the-art n-body algorithms incorporate individual (and variable) time-steps each particle in system gain additional efficiency, starts complicated!

hope helps.