Рыхлое октодерево
Вариант октодерева, у которого границы узлов расширены, так что объект, лежащий на границе, целиком помещается в один узел.
У обычного октодерева есть неприятная особенность: объект, лежащий поперёк плоскости разбиения, приходится либо хранить высоко в дереве, либо делить между несколькими узлами. Рыхлое октодерево решает это «ослаблением» границ каждого узла — как правило, длина стороны удваивается, — и они перекрываются с соседями. Объект помещается в тот узел, куда попадает его центр, и целиком входит в него, где бы ни находился.
Этот приём описал Тэтчер Ульрих в Game Programming Gems (2000). Расплата в том, что при каждом запросе проверяются чуть более крупные боксы, зато вставка и обновление просты и дёшевы — идеально для движущихся объектов, где строгое дерево пришлось бы постоянно перестраивать.