Квадродерево (quadtree)
Двумерный родственник октодерева: раз за разом делит плоскость на четыре квадранта, чтобы не сравнивать каждый объект с каждым.
Описано Рафаэлем Финкелем и Джоном Бентли в 1974 году. Каждый объект попадает в наименьший квадрант, который его вмещает, а запрос по области обходит только пересекающиеся узлы, превращая попарное сравнение из квадратичного в логарифмическое.
Применяется в 2D-играх, геоинформационных системах, сжатии изображений и broad-phase столкновений. «Свободное» (loose) квадродерево оставляет объекты, пересекающие границу, в родительском узле, а не разрезает их, что избавляет от дорогой пересортировки при движении.