kd-tree
Un albero binario che partiziona lo spazio a k dimensioni alternando l'asse di divisione a ogni livello.
Inventato da Jon Bentley nel 1975. Alla radice i punti vengono divisi lungo x, al livello successivo lungo y, poi z, e così via ciclicamente; dividendo sul punto mediano si ottiene un albero bilanciato. Ricerche del vicino più prossimo e interrogazioni per intervallo diventano così logaritmiche anziché lineari.
I kd-tree si usano per nuvole di punti, photon mapping e come struttura di accelerazione nel ray tracing di scene statiche. Per i mondi di gioco in movimento si preferisce una BVH, perché ricostruire un kd-tree a ogni fotogramma è costoso.