Drzewo kd
Drzewo binarne dzielące przestrzeń k-wymiarową, w którym oś podziału zmienia się cyklicznie z poziomu na poziom.
Wynalazł je Jon Bentley w 1975 roku. W korzeniu punkty dzieli się wzdłuż osi x, na następnym poziomie wzdłuż y, potem z i znów od początku — podział w punkcie mediany daje drzewo zrównoważone. Dzięki temu wyszukiwanie najbliższego sąsiada i zapytania zakresowe mają złożoność logarytmiczną zamiast liniowej.
Drzewa kd stosuje się do chmur punktów, photon mappingu i jako strukturę przyspieszającą ray tracing statycznych scen. W ruchomych światach gier woli się BVH, bo przebudowa drzewa kd w każdej klatce jest kosztowna.