Point Quadtree

A point quadtree is a tree data structure that stores spatial points by recursively subdividing a two-dimensional plane into four quadrants. Each point occupies a node, and the four children of that node represent the northwest, northeast, southwest, and southeast quadrants relative to the point's coordinates. Invented by Raphael Finkel and Jon Bentley in 1974, the point quadtree is the spatial analog of the binary search tree, though it partitions in both dimensions simultaneously rather than alternating.

Point quadtrees support efficient range queries and nearest-neighbor searches in two dimensions, but they share the binary search tree's vulnerability to pathological inputs: clustered points produce unbalanced trees with worst-case linear depth. Unlike the k-d tree, which splits along alternating dimensions, the point quadtree splits in both dimensions at every level, producing a more symmetric but less flexible structure.

The point quadtree is rarely the best choice for any particular application, yet it remains the first spatial index taught in most algorithms courses. This is not an accident. The point quadtree's clarity as a teaching tool obscures its mediocrity as an engineering tool — a pattern that repeats throughout computer science education, where pedagogical elegance and practical performance are systematically confused.