[sdbrown]

A k-D tree?

[contravariant]

That's a binary tree where each node divides the space along a single axis. A quad-, oct-, 2^n-tree divides along all axes for every node.

[geophile]

No. Quad and octtrees divide the space. K-d trees divide the data.

[snovv_crash]

kD-tree doesn't necessarily split at the midpoint like a quad or oct-tree do.