Quadtree
The octree's two-dimensional sibling — it divides a plane into four quadrants over and over to avoid testing everything against everything.
Described by Raphael Finkel and Jon Bentley in 1974. Each object goes into the smallest quadrant that holds it, and a region query visits only the overlapping nodes — turning an all-pairs comparison from quadratic into logarithmic.
It shows up in 2D games, geographic information systems, image compression and collision broad-phase. A "loose" quadtree lets objects straddling a boundary stay in the parent node rather than being split, which avoids costly re-sorting as things move.