Thursday, June 23, 2011

The Barnes-Hut Algorithm

The Barnes-Hut Algorithm: "The crucial idea in speeding up the brute force n-body algorithm is to group nearby bodies and approximate them as a single body. If the group is sufficiently far away, we can approximate its gravitational effects by using its center of mass. The center of mass of a group of bodies is the average position of a body in that group, weighted by mass. Formally, if two bodies have positions (x1, y1) and (x2, y2), and masses m1 and m2, then their total mass and center of mass (x, y) are given by:"