Range searching and kd-trees

At a node, split the points near the median of the current axis and cycle to the next axis at the following level. Store one point per leaf, and associate each node with its spatial cell and optionally a tighter bounding box of its points. Balanced partitioning gives logarithmic height and linear total nodes. Presorted coordinate lists with linear-time partitioning, or appropriate linear-time selection at each level, give sorting-scale construction; independently sorting every recursive subset would need a different cost analysis.

To answer a box query, reject a node whose enclosing region is disjoint from the query, accept its entire canonical subset if the region is contained, and otherwise recurse. A leaf still requires an exact membership test. Counting can use a cached subtree count when accepting a whole subset; reporting must write every returned point. Tighter bounding boxes can improve pruning but cannot invalidate the conservative cell tests. Equal coordinates and cut-boundary coincidences require a tie-aware partition and query convention rather than assuming that all geometric regions are disjoint closed boxes.

In two dimensions, consider a vertical query boundary passing through a cyclic balanced tree. At a vertical split it enters at most one relevant child; at a horizontal split it can enter both. Across two levels, the number of candidate branches doubles while their point counts fall by about a factor of four. This produces a square-root boundary-crossing bound. The rectangle has only four sides, so their total contribution remains square-root scale; the returned points contribute the separate output term.

In fixed higher dimension, the analogous cyclic argument gives the exponent shown above. The constants depend on dimension, and the exponent approaches one as dimension grows. Consequently a kd-tree is not a dimension-independent logarithmic range structure. Different split rules, including longest-side or arbitrary adaptive choices, may have different theoretical guarantees even when they work well in practice. Balance by itself is insufficient for this geometric analysis; the axis schedule is part of the theorem.

For nearest-neighbor search, one can compare the current best distance with a lower bound on distance to a node's box. Rejecting a box whose lower bound is too large is correct, but does not guarantee logarithmic worst-case work. Adversarial configurations can make an exact search inspect a linear number of points, even in a fixed low dimension. Distributional assumptions or an approximation tolerance can support other guarantees, but they must be named and proved separately.

Coordinate transformations also matter. An invertible shear preserves point incidence and convexity, yet an axis-aligned query becomes a parallelogram. Its axis-aligned enclosing box can be much larger than the transformed query, weakening pruning. A range bound for orthogonal boxes cannot simply be relabeled as the same theorem for arbitrary rotated or sheared shapes. The practical data structure should be chosen around the query family, output type, dimension, and acceptable approximation, rather than around a familiar tree name alone.