kd-boom (kd-tree)
Een binaire boom die de k-dimensionale ruimte opdeelt door op elk niveau de splitsingsas te laten rouleren.
Bedacht door Jon Bentley in 1975. Bij de wortel worden de punten langs x gesplitst, op het volgende niveau langs y, dan z, en daarna weer van voren af aan. Splitsen op het mediaanpunt geeft een gebalanceerde boom. Daardoor worden zoekopdrachten naar de dichtstbijzijnde buur en bereikquery's logaritmisch in plaats van lineair.
kd-bomen worden gebruikt voor puntenwolken, photon mapping en als versnellingsstructuur bij raytracing van statische scènes. Voor bewegende gamewerelden gaat de voorkeur uit naar een BVH, omdat kd-bomen duur zijn om elk frame opnieuw op te bouwen.