Our website is made possible by displaying online advertisements to our visitors.
Please consider supporting us by disabling your ad blocker.
Arbre kd
Arbre 2-d correspondant à la partition de l’espace (à dimension 2) au-dessus.
En informatique, un arbre k-d (ou k-d tree, pour k-dimensional tree) est une structure de données de partition de l'espace permettant de stocker des points, et de faire des recherches (recherche par plage, plus proche voisin, etc.) plus rapidement qu'en parcourant linéairement le tableau de points. Les arbres k-d sont des cas particuliers d'arbres BSP (binary space partition trees).
Cette structure a été proposée par Jon Louis Bentley de l'Université Stanford en 1975[1].
- ↑ (en) J. L. Bentley, « Multidimensional binary search trees used for associative searching », Communications of the ACM, vol. 18, no 9, , p. 509-517 (DOI 10.1145/361002.361007)
Previous Page Next Page
