kd-дерево
Двоичное дерево, разбивающее k-мерное пространство так, что ось разделения меняется по кругу на каждом уровне.
Изобретено Джоном Бентли в 1975 году. В корне точки делятся по x, на следующем уровне — по y, затем по z и снова по кругу; деление по медианной точке даёт сбалансированное дерево. Благодаря этому поиск ближайшего соседа и запросы по диапазону становятся логарифмическими, а не линейными.
kd-деревья применяют для облаков точек, photon mapping и как ускоряющую структуру при трассировке лучей в статичных сценах. Для движущихся игровых миров предпочитают BVH: kd-дерево дорого перестраивать каждый кадр.