Quadtree
El hermano bidimensional del octree — divide un plano en cuatro cuadrantes una y otra vez para evitar probar todo contra todo.
Descrito por Raphael Finkel y Jon Bentley en 1974. Cada objeto va al cuadrante más pequeño que lo contiene, y una consulta por región visita solo los nodos que se solapan — convirtiendo una comparación de todos contra todos de cuadrática en logarítmica.
Aparece en juegos 2D, sistemas de información geográfica, compresión de imágenes y el broad-phase de colisiones. Un quadtree "holgado" (loose) deja que los objetos a caballo sobre un límite permanezcan en el nodo padre en vez de partirse, lo que evita reordenaciones costosas cuando las cosas se mueven.