Mientras tanto, en los árboles BSP son las hojas los únicos nodos que contienen puntos (u otras primitivas geométricas).Las letras k y d se escriben en minúsculas, incluso al principio de una oración.Usar un árbol kd para encontrar todos los puntos que se encuentran en un rectángulo determinado (o análogo de más dimensiones).En las regresiones locales es común evaluar la superficie contenida directamente solo por los vértices del árbol kd e interpolar en algún punto.Este uso, reflejado en la imagen de arriba, busca asegurar que sólo se realizarán las evaluaciones directas necesarias.Como los árboles kd se "adaptan" al espacio, este método puede suministrar una excelente aproximación a las verdaderas superficies de regresión local.
Un árbol
k
d tridimensional. La primera división (rojo) corta la celda raíz (blanco) en dos subceldas, que son divididas a su vez (verde) en dos subceldas. Finalmente, cada una de esas cuatro es dividida (azul) en dos subceldas. Dado que no hay más divisiones, las ocho finales se llaman hojas. Las esferas amarillas representan los nodos del árbol.
En esta animación se representa como se busca el punto más próximo a otro punto dado (marcado en rojo). Aquí, el árbol ya está construido, cada vértice corresponde a un rectángulo, cada rectángulo se divide en dos subrectángulos iguales, y las hojas corresponden a rectángulos que contienen un solo punto.
