Arbre d'axes principaux - Définition
La liste des auteurs de cet article est disponible ici.
Recherche dans l'arbre
L'arbre est analysé depuis sa racine pour déterminer dans quelle région (et donc dans quel nœud fils) se trouve le point dont on cherche le voisinage. Cette analyse est aisément effectuée en projetant ledit point sur l'axe principal associé au nœud racine et en effectuant une recherche dichotomique parmi les limites des nc régions.
Ce processus est répété sur le nœud correspondant à la région en question et ainsi de suite jusqu'à atteindre une feuille que nous appellerons nœud terminal. Un algorithme de recherche de distance partielle est alors appliqué sur l'ensemble des points appartenant à ce nœud terminal.
L'algorithme remonte ensuite au nœud parent et tente d'éliminer les nœuds frères via le critère d'élimination :
- Si le critère est satisfait, les nœuds frères sont éliminé et l'analyse remonte au nœud parent ;
- Si le critère n'est pas satisfait, l'algorithme descend dans le nœud frère le plus proche pour une analyse plus approfondie.
Lorsque le nœud racine est complètement analysé (avec un mélange d'exploration et d'élimination), le voisinage est considéré comme construit.
En résumé, on part de la racine, on descend vers le nœud terminal correspondant au point dont on cherche le voisinage et on tente d'éliminer des sections entières de l'arbre via le critère délimination.
