Октодерево (octree)
Дерево, которое раз за разом делит трёхмерное пространство на восемь ячеек, чтобы проверять только объекты, действительно находящиеся рядом.
Каждый узел — куб с восемью потомками, по одному на октант. Объект попадает в наименьший куб, который его вмещает, а запросу по области достаточно обойти кубы, которые она пересекает. Глубина подстраивается под плотность: пустые участки мира остаются неглубокими.
Структура лежит в основе broad-phase столкновений, frustum culling и хранения вокселей (как в мирах в духе Minecraft) и облаков точек. Двумерный аналог — квадродерево, и выбор между ними сводится к тому, по скольким осям нужно делить мир.