kd-träd
Ett binärt träd som delar k-dimensionellt rum genom att växla delningsaxel på varje nivå.
Uppfunnet av Jon Bentley 1975. På rotnivån delas punkterna längs x, på nästa nivå längs y, sedan z, och så runt igen — varje delning vid medianpunkten ger ett balanserat träd. Det gör närmaste-granne-sökningar och områdesfrågor logaritmiska i stället för linjära.
kd-träd används för punktmoln, fotonmappning och som accelerationsstruktur i strålspårning av statiska scener. För rörliga spelvärldar föredras BVH, eftersom kd-träd är dyra att bygga om varje bildruta.