![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Arvore_vp.png/640px-Arvore_vp.png&w=640&q=50)
Vantage point tree
De Wikipedia, l'encyclopédie encyclopedia
Un arbre à points de vue (ou vp-tree, abréviation de l'appellation anglaise vantage point tree) est un arbre métrique permettant de partitionner n'importe quel espace de données pourvu d'une métrique, c'est-à-dire d'une mesure de distance entre les nœuds ou points représentant les données. Le processus de construction de l'arbre consiste à sélectionner un point privilégié (ledit point de vue ou point d'observation / de référence, vantage point en anglais), puis à diviser l'espace en deux sous-espaces : un sous-espace gauche (ou intérieur) contenant l'ensemble des points à une distance du point privilégié inférieure à un certain seuil, et un sous-espace droit (ou extérieur) contenant l'ensemble des points ne remplissant pas cette condition. Le processus est appliqué de manière récursive, produisant des sous-espaces de plus en plus petits. Le vp-tree résultant est une structure de données arborescente telle qu'une proximité dans l'arbre est représentative de la proximité dans l'espace de données ainsi partitionné.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Arvore_vp.png/640px-Arvore_vp.png)
Ce processus de partitionnement itératif est similaire à celui d'un k-d tree, mais utilise des partitions circulaires (ou sphériques, hypersphériques, etc. selon la dimension de l'espace) plutôt que rectilignes. Dans un espace euclidien bidimensionnel, il produit un découpage en régions dont la forme ressemble à des coquilles sphériques[1].