Sobre elentrada de wikipedia para k-d trees, se presenta un algoritmo para hacer una búsqueda de vecino más cercano en un árbol k-d. Lo que no entiendo es la explicación del paso 3.2. ¿Cómo sabe que no hay un punto más cercano solo porque la diferencia entre la coordenada de división del punto de búsqueda y el nodo actual es mayor que la diferencia entre la coordenada de división del punto de búsqueda y la mejor actual?

Búsqueda de vecinos más cercanos Animación de NN buscando con un árbol KD en 2D

El algoritmo del vecino más cercano (NN) tiene como objetivo encontrar el punto en el árbol que está más cercano a un punto de entrada dado. Esta búsqueda se puede hacer de manera eficiente utilizando las propiedades del árbol para eliminar rápidamente grandes porciones del espacio de búsqueda. La búsqueda de un vecino más cercano en un kd-tree procede de la siguiente manera:

Comenzando con el nodo raíz, el algoritmo se mueve hacia abajo en el árbol de forma recursiva, de la misma manera que lo haría si se inserta el punto de búsqueda (es decir, va hacia la derecha o hacia la izquierda dependiendo de si el punto es mayor o menor que el nodo actual en el dimensión dividida).Una vez que el algoritmo alcanza un nodo de hoja, guarda ese punto de nodo como el "mejor actual"El algoritmo desenrolla la recursión del árbol, realizando los siguientes pasos en cada nodo: 1. Si el nodo actual está más cerca que el mejor actual, entonces se convierte en el mejor actual. 2. El algoritmo verifica si podría haber puntos en el otro lado del plano de división que estén más cerca del punto de búsqueda que el mejor actual. En concepto, esto se hace intersectando el hiperplano de división con una hiperesfera alrededor del punto de búsqueda que tiene un radio igual a la distancia más cercana actual. Dado que todos los hiperplanos están alineados con el eje, esto se implementa como una comparación simple para ver si la diferencia entre la coordenada de división del punto de búsqueda y el nodo actual es menor que la distancia (coordenadas generales) desde el punto de búsqueda hasta la mejor posición actual. 1. Si la hiperesfera cruza el plano, podría haber puntos más cercanos en el otro lado del plano, por lo que el algoritmo debe moverse hacia abajo en la otra rama del árbol desde el nodo actual en busca de puntos más cercanos, siguiendo el mismo proceso recursivo que el Toda la búsqueda. 2. Si la hiperesfera no se cruza con el plano de división, entonces el algoritmo continúa subiendo por el árbol y se elimina toda la rama del otro lado de ese nodo.Cuando el algoritmo finaliza este proceso para el nodo raíz, la búsqueda se completa.

En general, el algoritmo usa distancias cuadradas para comparar y evitar el cálculo de raíces cuadradas. Además, puede guardar el cálculo manteniendo la mejor distancia de la corriente al cuadrado en una variable para comparación.