Barnes' Hut manages to compute approximate pairwise forces in N lg N time in total, which is pretty good.
However, we can do even better.
https://en.wikipedia.org/wiki/Fast_multipole_method
The fast multipole method can approximate the forces in just O(N) time, which is pretty remarkable.
woohoo
I was a little confused about this, so: each node in the tree represents not a body, but a space. "The topmost node represents the whole space, and its four children represent the four quadrants of the space. As shown in the diagram, the space is recursively subdivided into quadrants until each subdivision contains 0 or 1 bodies (some regions do not have bodies in all of their quadrants." More details here: http://arborjs.org/docs/barnes-hut
Barnes' Hut manages to compute approximate pairwise forces in N lg N time in total, which is pretty good. However, we can do even better. https://en.wikipedia.org/wiki/Fast_multipole_method The fast multipole method can approximate the forces in just O(N) time, which is pretty remarkable.
I was a little confused about this, so: each node in the tree represents not a body, but a space. "The topmost node represents the whole space, and its four children represent the four quadrants of the space. As shown in the diagram, the space is recursively subdivided into quadrants until each subdivision contains 0 or 1 bodies (some regions do not have bodies in all of their quadrants." More details here: http://arborjs.org/docs/barnes-hut