árbol kd
Un árbol binario que particiona el espacio k-dimensional alternando el eje de corte en cada nivel.
Inventado por Jon Bentley en 1975. En la raíz los puntos se dividen a lo largo de x, en el siguiente nivel a lo largo de y, luego z, y vuelta a empezar — cortar por el punto mediano da un árbol equilibrado. Eso vuelve logarítmicas, en lugar de lineales, las búsquedas del vecino más cercano y las consultas por región.
Los árboles kd se usan para nubes de puntos, photon mapping y como estructura de aceleración en el trazado de rayos de escenas estáticas. Para mundos de juego en movimiento se prefiere una BVH, ya que los árboles kd son caros de reconstruir en cada fotograma.