CoreSource checked

Barnes-Hut Simulation

Approximates many-body forces by grouping distant bodies in a spatial tree.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Simulation
Difficulty: Intermediate
Family: N-Body Simulation
Tier: Core
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 5
Code example: Ready
Visualization: Ready

Overview

Barnes-Hut Simulation builds a quadtree or octree, summarizes distant cells by their center of mass, and uses that summary when a cell is sufficiently far from the body being updated.

Core Concepts

approximate n-body simulationn-body simulationspatial approximationsimulation

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n log n)

Worst

O(n^2)

Space

O(n)

When to Use

Use it when all-pairs force computation is too expensive.
Use it when approximate long-range interactions are acceptable.
Use smaller opening angles when accuracy matters more than speed.

When Not to Use

Avoid it when exact pairwise forces are required.
Avoid it when bodies are so few that tree overhead dominates.
Avoid loose error settings in unstable simulations.

What It Does

Approximates n-body interactions
Uses a spatial tree and opening-angle criterion

Use Cases

Gravity-like n-body simulation
Particle systems with long-range forces
Teaching hierarchical approximation

Inputs

Particle positions x_i, masses/charges m_i, and velocities v_i
Spatial tree opening angle θ or multipole expansion order p

Outputs

Net gravitational or electrostatic force/acceleration vectors a_i
Hierarchical octree/quadtree multipole moments

Key Formulas (1)

Opening criterion

s / d < θ

s / d < theta

Approximates a distant cell when its size is small relative to distance.

Pseudocode

1.Initialize the input structures and parameters for Barnes-Hut Simulation (approximate n-body simulation).
2.Set up the working state for n-body simulation (n-body simulation).
3.Execute the core step by their center of mass, and uses that summary when a cell is sufficiently far from the body being updated (s / d < theta).
4.Update invariants and check termination or convergence criteria.
5.Return the resulting n-body simulation output.

Canonical Example

Input: one particle and a distant cluster of many particles
Output: approximate force from the cluster's center of mass
Explanation: If the cluster is far enough relative to its size, the simulation uses one summarized interaction.

Implementation Notes

Build a spatial tree over bodies each step or update it carefully.
Store total mass and center of mass for each internal cell.
Use the opening-angle test to decide whether to approximate or descend.

Common Pitfalls

Using an opening angle that is too large for the required accuracy.
Failing to rebuild or update the tree as particles move.
Letting very close interactions become numerically unstable.

Interactive Mechanism Walkthrough

Iterative Convergence & State Trajectory

Show approximating distant particle groups with a hierarchical tree on a small approximate n-body simulation example.

Step 1 of 5: Initialize the input structures and parameters for Barnes-Hut Simulation (approximate n-body simulation).

simulation-mechanism

Notes

Barnes-Hut Simulation operates in O(n log n) time and O(n) space within the N-Body Simulation family. Key governing relation: s / d < theta. Often compared with Fast Multipole Method and Verlet Neighbor List.