An Analysis of Random d-Dimensional Quad Trees

Devroye, Luc et Laforest, Louise (1990). « An Analysis of Random d-Dimensional Quad Trees ». SIAM Journal on Computing, 19(5), pp. 821-832.

Fichier(s) associé(s) à ce document :

Prévisualisation	PDF Télécharger (1MB)

Résumé

It is shown that the depth of the last node inserted in a random quad tree constructed from independent uniform $[0,1]^d $ random vectors is in probability asymptotic to $({2 / d}) \log n$, where log denotes the natural logarithm. In addition, for $d = 2$, exact values are obtained for all the moments of the depth of the last node.

Type:	Article de revue scientifique
Mots-clés ou Sujets:	average time analysis, probability inequalities, random quad tree, multidimensional data structures, search tree, expected behavior, analysis of algorithms
Unité d'appartenance:	Faculté des sciences > Département d'informatique
Déposé par:	Louise Laforest
Date de dépôt:	18 avr. 2016 14:16
Dernière modification:	27 avr. 2016 18:13
Adresse URL :	http://archipel.uqam.ca/id/eprint/8166

Modifier les métadonnées (propriétaire du document)

Statistiques