Quadtrees & Octrees

Imagine dropping a million GPS pins on a map and then asking: "which pins are inside this rectangle?" The brute-force answer checks all one million. But real maps respond in milliseconds. The secret is a quadtree.

A quadtree is a tree in which every internal node represents a square region of 2-D space and has exactly four children — one for each quadrant: NW, NE, SW, SE. When a region contains too many points it gets subdivided, splitting into four smaller squares. Regions that are empty or sparse stay as leaves and are never touched during a search.

The result is a tree that mirrors the density of your data: crowded cities are represented by deep chains of tiny cells; empty oceans are a single leaf node. A spatial query descends only the branches that overlap the query region, skipping everything else.

Extending the idea to three dimensions gives an octree: each node splits a cube into eight sub-cubes (octants). The logic is identical; the branching factor doubles. Octrees are the workhorse of 3-D rendering, LiDAR point clouds, and physics engines.

Both structures trace back to Raphael Finkel and Jon Bentley (1974), who introduced the quad-tree for efficient 2-D range searching. They are now so ubiquitous that every major game engine, GIS platform, and graphics library ships them as a built-in primitive.

Click anywhere on the canvas to drop a point. The quadtree will subdivide that region as soon as it holds more than 4 points. Drag the orange query rectangle to highlight which cells the tree must visit — notice how it skips every cell that doesn't overlap.

<p class="hint">{{hint}}</p>
<canvas id="qt" width="380" height="320"></canvas>
<div class="info" id="info">{{info_initial}}</div>
<div class="btns">
  <button id="clear" type="button" class="ghost">{{btn_clear}}</button>
  <button id="rain" type="button">{{btn_rain}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; border: 1.5px solid #cdd9e3; border-radius: 8px; cursor: crosshair;
         background: #f7fafc; touch-action: none; max-width: 100%; }
.info { font-size: .88rem; color: #555; margin: .5rem 0 .4rem; min-height: 1.3em; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui,sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

The green cells are leaves the query touches; the rest are pruned entirely. With a uniform cloud of points you'll need $O(\log n)$ cell visits for a small query — far fewer than the n points themselves. Cluster all your points in one corner and the tree grows deep there, staying flat everywhere else.

Quadtrees are a solved, efficient algorithm — no open-problem status here. Their complexity is well-understood:

• Construction: inserting n points one by one costs $O(n \log n)$ expected time on uniformly distributed data. Each insertion descends the tree in O(depth) time, and depth averages $O(\log n)$.
• Range query: given a rectangular query window, the tree visits only the cells that overlap it. On n uniformly distributed points, a window enclosing k points touches $O(\sqrt{n} + k)$ leaf cells — dramatically less than n. In the worst case (adversarial clustering) depth can reach $O(n)$ and the whole advantage disappears.
• Depth guarantee: if the smallest pairwise distance between any two points is δ and the root spans a region of diameter D, the maximum depth is O(log(D/δ)) — depends on the spread of the data, not just its count.
• Nearest-neighbor search: find the closest point to a query in $O(\log n)$ expected time by pruning branches whose minimum distance to the query exceeds the current best.
• Octrees share the same asymptotic bounds in 3-D; the branching factor 8 versus 4 adds only a constant.

The practical takeaway: quadtrees excel on spatially coherent, moderately clustered data. For highly skewed or adversarial point sets, a k-d tree or R-tree often performs better. For uniformly random data they are nearly optimal.

The "divide space, skip the empties" idea turns up in an extraordinary range of fields:

• Collision detection in games: every physics engine partitions the world into cells. Objects that occupy different cells can't collide — test only pairs that share a cell. Quadtrees (2-D) and octrees (3-D) cut the $O(n^{2})$ naive check to near-linear for typical scenes.
• Map tiles and GIS: web maps store geographic features in a quadtree so that a pan or zoom only fetches the relevant tiles. The famous Google Maps tile scheme is essentially a quadtree of the Earth.
• Image compression: quadtree image coding recursively splits a region until each leaf is "uniform enough," storing one color per leaf instead of every pixel. The classic QTVQ (quadtree vector quantization) algorithm exploits this.
• LiDAR and 3-D point clouds: autonomous vehicles collect hundreds of millions of 3-D points per second. Octrees index them so that object detection queries run in milliseconds rather than hours.
• Mesh generation: finite-element solvers use quadtrees/octrees to generate adaptive meshes — fine cells where geometry is complex, coarse cells where it's flat.
• Barnes-Hut galaxy simulation: the famous $O(n \log n)$ gravity algorithm stores stars in an octree and approximates distant clusters as single masses, making million-body simulations tractable.

Any time you need to answer "what's near here?" efficiently, you're likely looking for a quadtree or its 3-D sibling. They are the unsung backbone of closest-pair algorithms and spatial reasoning everywhere.

Quadtrees and octrees embody one of the most powerful ideas in algorithm design: don't look where you don't have to. By mirroring the density of data in the structure of the tree, they convert hopeless $O(n)$ spatial searches into efficient $O(\log n)$ or $O(\sqrt{n})$ ones.

The construction is elegant, the guarantees are solid, and the applications span games, maps, robotics, graphics, and simulation. Every map you pan, every collision your game prevents, every LiDAR scan a self-driving car processes — there is a quadtree or an octree quietly doing the heavy lifting.

If you want to go deeper, look at how these structures relate to the closest-pair problem or how Barnes-Hut simulation turns the same idea into an $O(n \log n)$ gravity solver. Recursive space subdivision is a lens that sharpens almost any spatial problem you point it at.