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 :
[img]
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://www.archipel.uqam.ca/id/eprint/8166

Statistiques

Voir les statistiques sur cinq ans...