Quadtree
Il fratello bidimensionale dell'octree: divide ripetutamente un piano in quattro quadranti per evitare di confrontare tutto con tutto.
Descritto da Raphael Finkel e Jon Bentley nel 1974. Ogni oggetto va nel quadrante più piccolo che lo contiene e una query su una regione visita solo i nodi sovrapposti, trasformando il confronto fra tutte le coppie da quadratico a logaritmico.
Compare nei giochi 2D, nei sistemi informativi geografici, nella compressione di immagini e nella broad-phase delle collisioni. Un quadtree «loose» lascia nel nodo padre gli oggetti a cavallo di un confine invece di spezzarli, evitando costosi riordinamenti quando le cose si muovono.