🌳 Barnes-Hut Algorithm

The Barnes-Hut algorithm is a hierarchical approximation technique that speeds up n-body simulations — where every particle exerts gravitational or electrostatic force on every other particle — from the naive O(n²) pairwise cost down to O(n log n). It recursively subdivides space into a quadtree (2D) or octree (3D), and when a group of distant particles is small enough relative to its distance from a target particle, the whole group is treated as a single point mass at its center of mass rather than summed individually. Introduced by Josh Barnes and Piet Hut in 1986, the algorithm makes galaxy-scale and large-particle simulations computationally feasible on ordinary hardware, trading a small, tunable amount of accuracy for a dramatic reduction in computation as particle counts grow. Whether a cluster is "far enough" to approximate is controlled by an opening-angle threshold θ: a smaller θ demands stricter accuracy and forces the algorithm to descend deeper into the tree before approximating, while a larger θ approximates more aggressively and runs faster at the cost of some numerical error. This tunable trade-off is why Barnes-Hut, rather than a brute-force pairwise sum, underlies most real-time galaxy, star-cluster and particle-electrostatics simulations that need to scale past a few thousand bodies.