Quand faut-il visiter l'autre côté ?

La descente seule se trompe. À la racine, $q_x=7\le 7$ : on part à gauche. En $(5,4)$, $q_y=0\le 4$ : encore à gauche, jusqu'à $(2,3)$. En remontant on garde le meilleur des trois nœuds traversés, soit $(7,2)$, à distance $2$. Or le vrai plus proche voisin est $(8,1)$, à distance $\sqrt{2}\approx 1,414$ — et il est de l'autre côté du premier hyperplan.

Le test d'élagage. Soit $r$ la distance au meilleur candidat courant. Un nœud coupe l'espace par l'hyperplan d'équation $x_{\text{axe}}=p_{\text{axe}}$. Tout point du demi-espace opposé est à distance au moins $|q_{\text{axe}}-p_{\text{axe}}|$ de $q$. Donc :

$$\text{si }|q_{\text{axe}}-p_{\text{axe}}|\ge r,\text{on eˊlague ;}\text{sinon, on doit explorer.}$$

Sur notre requête, à la racine $|7-7|=0<2$ : il faut explorer à droite, et c'est là qu'on trouve $(8,1)$. La recherche complète visite $5$ des $6$ points ; le seul élagué est $(4,7)$, coupé en $(5,4)$ car $|0-4|=4\ge 2$.

Ce que l'exercice éprouve. L'arbre $k$-d n'est pas un arbre binaire de recherche où la descente suffirait. Le test de la racine sépare selon une seule coordonnée, et le plus proche voisin peut se trouver juste de l'autre côté du plan de coupe. La descente donne un candidat, jamais une réponse ; c'est la remontée avec élagage qui rend l'algorithme exact. L'élagage est ici le même geste qu'au chapitre chap:exploration : on ne coupe une branche qu'après avoir prouvé qu'elle ne peut rien contenir de meilleur.