Quadtree and k-d tree

In short: A quadtree and a k-d tree split space recursively into regions so that points near a position can be found quickly without checking them all.

In more detail: Both are spatial index structures. They answer “which points lie in this rectangle?” or “which point is nearest?” in about O(log n) instead of O(n).

In Depth

• Quadtree: Splits an area into four equal quadrants, which are split further as needed. Popular in games (collision checks), map tiles and image compression. The 3D variant is the octree.
• k-d tree: A binary tree splitting alternately by one coordinate (x, then y, then z, …) at the median. Good for nearest-neighbour search in low dimensions.
• Limit: In very many dimensions (about 20+) they lose their advantage (“curse of dimensionality”). Then one uses vector indexes with approximate methods.
• Related: R-trees for rectangles (PostGIS), geohash for maps.
• Moving objects: Must be removed from the tree and reinserted, which can be expensive.

See also: Binary search