A store locator keeps fifty thousand lat/long pins in an ArrayList. “Show everything in this viewport” walks the list and tests a box. Pan the map, walk them again. “Which pin is nearest this tap?” walks them a third time. Nobody wrote a nested loop by accident. They stored points in a shape that cannot skip a region.
A spatial tree splits space so a query can discard whole regions. Quadtrees cut a 2D box into four children and split when a region is too full. k-d trees split one axis at a time and walk the nearer side first for nearest neighbor. Terms this series will not re-teach — ADT vs implementation, how to read a complexity table — live on the Data Structures Roadmap. This post is the layout, not a GIS product walkthrough.
The nested loop the plane does not need
Range and nearest neighbor are the two questions that make a list of points feel slow. Both are honest on paper. Both scan n points unless the layout can prove a region is irrelevant.
List<Point> inViewport(List<Point> pins, Rect view) {
List<Point> hits = new ArrayList<>();
for (Point p : pins) {
if (view.contains(p)) {
hits.add(p);
}
}
return hits;
}
Point nearest(List<Point> pins, Point tap) {
Point best = null;
double bestDist = Double.POSITIVE_INFINITY;
for (Point p : pins) {
double d = distance(tap, p);
if (d < bestDist) {
bestDist = d;
best = p;
}
}
return best;
}Each call is O(n). Ten pans in a session are ten full scans. Pairwise “who is near whom?” is O(n²). A hash table does not help: there is no exact key. A TreeMap ordered by latitude still leaves longitude as a leftover scan.
A point and a query box are immutable carriers. Records fit:
public record Point(double x, double y) {}
public record Rect(double x, double y, double w, double h) {
boolean contains(Point p) {
return p.x() >= x && p.x() < x + w
&& p.y() >= y && p.y() < y + h;
}
boolean overlaps(Rect other) {
return x < other.x + other.w && x + w > other.x
&& y < other.y + other.h && y + h > other.y;
}
}The tree nodes below are mutable layouts — children get wired after construction — so they stay ordinary classes. The series rule is the same as for any node: records for the payload, a class for the wiring.
Quadtrees: four children and region occupancy
A quadtree node is a rectangle. In 2D that rectangle has at most four children — northwest, northeast, southwest, southeast — each covering one quadrant of the parent. There is no fifth direction. This is not a binary tree with leftover slots; arity is the split.
The occupancy rule decides when those children exist:
| Occupancy | Shape |
|---|---|
| Empty | Bounds, no points, no children. |
| Leaf | Bounds plus a small list of points, still under capacity. |
| Internal | Capacity was exceeded; four children own the points now. The parent list is empty. |
Capacity is a constant you pick (often 4 or 8). Insert walks to the leaf whose box contains the point. If that leaf is under capacity, the point stays there. If not, the leaf splits into four equal quadrants, existing points are re-binned, and insert continues. A region that never fills stays a leaf. A crowded corner becomes a deep cluster of small boxes. Empty quadrants stay empty — that is the prune.
[world]
┌─────────┼─────────┐
NW NE SW SE
│ │
[split] (leaf, 2 pts)
NW NE SW SEA node sketch:
public final class QuadNode {
static final int CAPACITY = 4;
final Rect bounds;
final List<Point> points = new ArrayList<>();
QuadNode nw, ne, sw, se;
QuadNode(Rect bounds) {
this.bounds = bounds;
}
boolean isLeaf() {
return nw == null;
}
}nw == null means “still a leaf.” After a split, all four children are allocated even if some stay empty. Empty children are cheap: a range query that does not overlap them never looks inside.
The range query is the occupancy rule in reverse. If the query rectangle does not overlap this node’s bounds, the whole subtree is skippable — every point in that region is outside the viewport. If it does overlap and the node is a leaf, test the few points that live here. If it is internal, recurse only into children that overlap.
void query(QuadNode node, Rect range, List<Point> hits) {
if (node == null || !range.overlaps(node.bounds)) {
return; // this region cannot contribute
}
if (node.isLeaf()) {
for (Point p : node.points) {
if (range.contains(p)) {
hits.add(p);
}
}
return;
}
query(node.nw, range, hits);
query(node.ne, range, hits);
query(node.sw, range, hits);
query(node.se, range, hits);
}That is why a tight viewport on a large map is cheap: most of the four-way split never runs. A query as big as the world still visits everything — the tree cannot invent a skip that geometry does not allow.
Note: Classic region quadtrees split into equal quadrants of the parent box. Point-quadtrees instead store one point per node and split relative to that point. Occupancy-plus-capacity is the region picture this post uses. Both prune boxes. Neither is a database, a map tile server, or a GIS suite.
Uniform points give a shallow tree. All points piled in one corner give a chain of splits that chase the pile — height can approach n. Insert is then no better than appending to a list, plus pointer overhead. The structure assumes the plane has empty space worth skipping.
Structure: region quadtree (2D, capacity C)
insert typical O(log n) if spread out; O(n) if all in one corner
range (viewport) O(log n + k) when most boxes miss; worst O(n)
nearest neighbor same prune idea; not the k-d tree's native walk
space O(n) points + internal boxes
arity 4 children; 2D
JDK none — you build this (or take a library)k-d trees: alternating axes and nearest neighbor
A k-d tree is a binary tree over points in k dimensions. Each level splits on one axis, then the next, cycling. In 2D: root splits on x, children on y, grandchildren on x again. Left of a node means “smaller on this axis”; right means “greater or equal.” There are not four children. There is one cutting plane, then two half-spaces.
depth % k == 0 → split on x
depth % k == 1 → split on y
depth % k == 2 → split on z (if you have a third coordinate)
left: point.axis < pivot.axis
right: point.axis >= pivot.axisBuilding by the median along the current axis keeps height O(log n): sort (or select) the points on that axis, pick the middle as the node, recurse on the two halves with depth + 1. Incremental insert into a leaf is simpler and can go lopsided, the same way a BST does under sorted keys. Median build is the usual “I have all the points up front” choice.
public final class KdNode {
final Point point;
KdNode left;
KdNode right;
KdNode(Point point) {
this.point = point;
}
}Range search still prunes: if the query box lies entirely to the left of this node’s splitting plane, skip the right child. The idea that made the quadtree cheap is unchanged. The shape is different — one axis per level, two children, k that is not stuck at 2.
Nearest neighbor is the walk this tree is known for. Visit the child that contains the query first (you might already be close). Remember the best point seen. On the way back, ask whether the other child’s splitting plane is closer than the current best distance. If the plane is farther than the best, every point on that side is farther still — skip it. If the plane cuts the best-so-far ball, the other side might win, so search it.
void nearest(KdNode node, Point q, int depth, Best best) {
if (node == null) {
return;
}
double d = distance(q, node.point);
if (d < best.dist) {
best.dist = d;
best.point = node.point;
}
int axis = depth % 2;
double delta = (axis == 0)
? q.x() - node.point.x()
: q.y() - node.point.y();
KdNode closer = delta < 0 ? node.left : node.right;
KdNode farther = delta < 0 ? node.right : node.left;
nearest(closer, q, depth + 1, best);
if (Math.abs(delta) < best.dist) {
nearest(farther, q, depth + 1, best);
}
}Best is a tiny mutable holder for the incumbent neighbor. Math.abs(delta) is the distance from the query to the splitting plane. That one comparison is the prune: if the other half-space cannot beat the incumbent, do not enter it.
In 2D with a median-built tree, that prune usually leaves an O(log n) walk. The worst case is still O(n): a query sitting in a dense cluster, or a skinny tree, can force almost every node to be visited. The table is a shopping list, not a guarantee on the next tap.
Structure: k-d tree (median build)
build O(n log n)
nearest neighbor expected O(log n) in low dimension; worst O(n)
range prune half-spaces that miss the box; worst O(n)
space O(n)
arity 2 children; k dimensions, one axis per level
JDK noneQuadtree vs k-d tree is a job match, not a ranking:
| Job | Lean toward |
|---|---|
| 2D map, viewport, “what’s in this box?” | Quadtree — occupancy matches the plane you drew |
| Nearest neighbor, 2D or a few extra dimensions | k-d tree — the plane-distance test is the walk |
| Many moving points, rebuild all the time | Often a uniform grid instead of either tree |
| Image / region occupancy (which cells are filled) | Quadtree |
When not to use a spatial tree
Skip both layouts when the geometry is not the hot path, or when the prune you are buying will not fire.
- Few points — nested loop. A few hundred pins in an
ArrayListis a tight scan. No pointer chasing, no split logic, no capacity constant to tune. The tree’s constants lose untilnis large enough that skipping regions dominates. Measure before you split the plane. - High dimensions — the curse. A k-d tree accepts
k > 2. Pruning does not. In high dimension, distances concentrate: nearest and farthest neighbors sit at similar radii, so the “other side of the plane” almost always intersects the best-so-far ball. You visit nearly every node and paid tree overhead for a scan. At that point brute force (or a different index: LSH, inverted lists) is the honest layout. Quadtrees do not save you either — four-way splits are a 2D occupancy story. - You needed a GIS product. PostGIS, tile servers, spherical earth, geohashes, and map SDKs are products and projections. This post is two in-memory trees over points in a plane. Do not treat a
QuadNodeas a substitute for a spatial database. - Points move every frame. Reinserting thousands of movers is a rebuild in slow motion. Games often use a fixed grid (or a loose quadtree they rebuild on a timer) because occupancy changes faster than a deep split stays valid.
- You only ever ask exact id lookup. That is a
HashMap. Coordinates are not keys unless you quantized them on purpose.
There is no java.util.QuadTree and no java.util.KdTree. Production Java reaches for a library or a database when the data set is large, persistent, or geographic. The sketches above are so you can see the prune, not so you ship them as a map stack.
Cheat sheet
Problem: range / nearest neighbor on points; a list scans n
Idea: split space; skip regions that cannot hold the answer
Quadtree: 2D box → 4 children (NW NE SW SE)
Occupancy: empty | leaf (under capacity) | internal (split)
Range: if query misses bounds, skip the subtree
k-d tree: binary; axis cycles (x, y, x, …)
NN: nearer child first; prune if plane is farther than best
Few points: nested loop (cache-friendly)
High k: prune dies — curse of dimensionality
JDK: noneDo:
- Name the query first: viewport range, or nearest neighbor, or both.
- Use a quadtree when the data is 2D and occupancy of boxes is the story.
- Use a k-d tree when nearest neighbor (in low dimension) is the hot walk.
- Keep points as records; keep nodes as mutable classes.
Don’t:
- Scan the whole list on every pan once
nis large and the viewport is small. - Reach for a k-d tree in dozens of dimensions and expect
O(log n). - Confuse these trees with a GIS product, a tile pyramid, or a spherical earth model.
- Split a handful of points into a tree because the name sounds advanced.
Wrap-up
Spatial trees exist because a list of points can only answer “near” by looking at every point. A quadtree is a 2D occupancy tree: four children, split when a box is too full, skip any box the query does not touch. A k-d tree is a binary tree that cycles through axes: nearer child first, prune the other when the splitting plane sits outside the best-so-far ball.
Use a nested loop when n is small. Use a quadtree for 2D range occupancy. Use a k-d tree for nearest neighbor in a handful of dimensions. Walk away when dimension is high enough that pruning stops firing. The glossary and the rest of the series stay on the Data Structures Roadmap.