Search tools and guides ⌘K
VII · Spatial structures

Quad-tree / Octree

Recursive 4-way / 8-way subdivision.

1974 · Raphael Finkel & Jon Bentley
The story

Recursively split 2D space (or 3D, for octree) into four (eight) equal quadrants. Each level halves resolution; deeper levels resolve dense regions. Used everywhere in graphics, physics simulation, and image processing.

How it works

Each node either stores the points in its quadrant directly (leaf), or has 4 children covering 4 sub-quadrants. Splits when point count exceeds a threshold. Search and insert recurse only into the relevant quadrants.

Where it lives

Image quadtree compression. Game-engine spatial partitioning. Procedural generation. Adaptive mesh refinement in physics simulations. Minecraft's chunk lookup uses something like an octree.

The key insight

Quadtrees adapt to data density — sparse regions stay shallow, dense regions get deeper. That's the property that makes them dominant in graphics and simulation.

More in Spatial structures
KD-tree Binary search, in higher dimensions. R-tree A tree of bounding boxes. BVH · bounding volume hierarchy A tree of boxes for ray tracing. Z-order / Hilbert curve Linearise space, preserve locality.
Across the cabinet
I Linked list A chain you can splice. I Stack Last in, first out. I Queue First in, first out. I Deque Both ends, equally. I Ring buffer A fixed-size queue that never allocates. II Binary search tree Sorted, but with shortcuts. II AVL tree Always height-balanced, to within one. II Red-black tree Almost balanced, much faster to maintain.
← All data structures