moteur de recherche

Séminaire Algo - Philippe Duchon
Séminaire Algo - Philippe Duchon
1-Dec-2020 14:00
Age: 3 days





Philippe Duchon

Analyse du pire cas probabiliste pour les quadtrees

Zoom (if you want to participate, please request the meeting password. If your interest in the seminar is more general, you can request to be added to the announcement mailing list which will contain the password for each meeting)

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)








<- Back to: Accueil