Quadtree Collision Detection

To find which of $N$ moving disks are touching, the obvious method checks every pair: $N(N-1)/2$ tests every step, an $O(N^2)$ cost that explodes as $N$ grows. A quadtree fixes it. The box is recursively split into four until each cell holds only a handful of disks, so each disk need only test the few others in its own and neighbouring cells. The cells subdivide wherever the disks crowd and stay coarse where the box is empty, tracking the crowd every frame. The scene shows the disks bouncing and colliding with the live quadtree over them; the diagnostic plots pair-checks against $N$, the $O(N^2)$ all-pairs parabola against the gentle $O(N\log N)$ quadtree. Same collisions found, far less work.

Figure 1. Quadtree-accelerated collision detection. Top: equal hard disks bouncing in a box with the adaptive quadtree overlaid, its cells subdividing where the disks crowd. Bottom: pair-checks per step versus N, the $O(N^2)$ all-pairs count against the measured $O(N\log N)$ quadtree count. Method: elastic disk collisions; a point quadtree (leaf capacity 4) queried with a neighbourhood box per disk.

N disks500

methodquadtree

show tree

WHAT TO TRY

Watch the quadtree subdivide finely where the disks crowd together and stay coarse in the empty gaps; it follows the disks every frame.
Switch the method to all pairs (N²): the grid vanishes and the pair-check count jumps onto the brute-force parabola, far above the quadtree, especially at large N.
Push N up and read the gap on the lower plot: the quadtree's check count creeps up like N log N while all-pairs climbs like N², the speedup the readout reports.