Résumé : Les quadtrees ("point quadtrees") sont un analogue multidimensionnel des arbres binaires de recherche, où un ensemble de points dans un espace de dimension d>1 sont représentés de manière hiérarchique par un arbre qui permet la recherche et l'insertion d'un nouveau point en un temps contrôlé par la hauteur de l'arbre. L'analyse probabiliste des quadtrees, réalisée dans les années 90 notamment par des méthodes analytiques, suppose généralement que les points sont pris aléatoirement (et uniformément) dans un domaine rectangulaire. Or, à la différence des arbres binaires de recherche, il ne suffit pas de randomiser l'ordre d'insertion pour assurer que ce modèle est pertinent: la loi de l'arbre obtenu par insertion dans un ordre aléatoire de ces points dépend significativement du nuage de points considéré. Nous montrons que, si l'on analyse la longueur de cheminement des arbres comme représentative du coût de construction du quadtree, on peut identifier exactement les pires nuages de points. C'est vrai en un sens probabiliste assez fort: la loi du cheminement total pour le pire cas domine, pour l'ordre stochastique, la loi du cheminement pour tout autre nuage de points. En particulier, aucun nuage de points n'a une longueur de cheminement moyenne plus grande que le 2n log(n) des arbres binaires de recherche. (Travail en commun avec Sophie Juppet)

Séminaire organisé par le LIGM.

Dernière modification : Monday 18 March 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr