Questions explications rapides et une démonstration des
arbres k-d, structure de données permettant notamment une
recherche rapide du plus proche voisin d'un point parmi un
ensemble de points donnés. Cette page ne traite que du cas
bidimensionnel, mais les différentes idées peuvent être
appliquées à des espaces de plus grande dimension.
Choisissez le nombre de points, générer des données, puis calculer l'arbre k-d.
Passez la souris sur l'image pour observer la structure de l'arbre et calculer le plus proche voisin du pointeur de la souris.
Cliquer sur un point de l'image pour voir le déroulement de l'algorithme (éventuellement pas à pas).
Points visités :
Définition et calcul de l'arbre k-d
L'algortithme ci-dessous calcule (et décrit) l'arbre k-d
d'un ensemble P de points du plan, étant donnée une direction (horizontale
et verticale).
ArbreKD(P, direction)
Si P est vide, renvoyer l'arbre vide.
Sinon, parmi les points de l'ensemble P , trouver le point p
occupant la position médiane dans la direction
(horizontale ou verticale) donnée. $(1)$
Calculer les ensembles $P_1$ et $P_2$ de
points situés à gauche et à droite (ou au
dessus et en dessous selon la direction) de p.
Renvoyer l'arbre binaire dont la racine est p, le sous-arbre gauche ArbreKD(P_1,direction') et le sous-arbre droit ArbreKD(P_2,direction') (ou direction' est horizontale si et seulement si direction est verticale).
Si l'étape $(1)$ est effectuée en complexité linéaire en la taille de l'ensemble de points (ce qui est possible en utilisant par exemple l'algorithme de sélection de Hoare), on montre que l'abre k-d d'un ensemble de $n$ points est construit en temps $O(n\log(n))$.
Recherche de plus proche voisin
Une fois l'arbre k-d d'un ensemble de points calculé,
on cherche à trouver le (un) plus proche voisin d'un
nouveau point $p$.
On commence par descendre dans l'arbre k-d
comme si on voulait insérer le nouveau point
$p$. Ce faisant, on calcule son plus proche voisin
parmi les points rencontrés. Cette étape
s'effectue en temps $O(\log(n))$ - i.e. en temps
proportionnel à la hauteur de l'arbre k-d. Cette
étape est observable passant la souris sur la
première figure ci-dessus. À noter que l'on
n'atteint pas nécessairement le plus proche
voisin ! (Celui ci est figuré en blanc.) Mais l'on en obtient une espèce d'«estimation»…
On remonte dans l'arbre k-d, en explorant si nécessaire les
autres branches rencontrées. C'est nécessaire s'il
peut y avoir un meilleur plus proche voisin de p que
celui qui a été pour l'instant trouvé dans le
demi-plan de l'autre côté de la droite
séparatrice correspondant au point où l'on se
trouve (ce qui se teste facilement en
regardant si l'intersection entre le demi-plan
et le «disque de recherche» où l'on pourrait
trouver un meilleur plus proche voisin est
non-vide).
On peut observer l'exécution de l'ensemble de
l'algorithme en cliquant sur un point de la première
figure ci-dessus. Une étude non-triviale montre que
l'on obtient une recherche de plus proche voisin de
complexité moyenne $O(\log(n))$ une fois l'arbre k-d
calculé (avec cependant une constante importante, qui
rend cet algorithme peu efficace face à des méthodes
plus naïves sur de «petits» ensembles de moins de
quelques milliers points).
Multidimensional binary search trees used for associative searching (Bentley) 1975. L'article introduisant les arbres k-d.
An Algorithm for Finding Best Matches in Logarithmic Expected Time (Friedman, Bentley, Finkel) 1976. Analyse de l'algorithme de recherche de plus proche voisin à l'aide d'un arbre k-d, et comparaison empirique avec des méthodes naïves basées sur la recherche linéaire.