Neat use of these is the "fast multipole method" for stimulating galaxies. If you want to compute the gravitational force on a given star exactly you need to f

Neat use of these is the "fast multipole method" for stimulating galaxies. If you want to compute the gravitational force on a given star exactly you need to figure out the forces from all other stars and add them up. This will be n^2 and slow. But turns out you can get a good approximation by dividing up space with a kd tree and using the average force from each cell to represent the stars underneath it in the tree. This gets you to nlogn https://en.m.wikipedia.org/wiki/Fast_multipole_method https://en.m.wikipedia.org/wiki/Fast_multipole_method