On the distribution of the arity of the root of a \(d\)-dimensional quadtree
type: Item
instance of: scholarly article
title: On the distribution of the arity of the root of a \(d\)-dimensional quadtree
zbMATH Open document ID: 0821.60019
DOI: 10.1016/0012-365X(94)00137-8
author: Gilbert Labelle
author: Louise Laforest
published in: Discrete Mathematics
publication date: 1995-09-27T00:00:00Z
review text: Soit \(\pi_{n, k, d}\) la probabilité qu'une sous-arborescence fixée de la racine d'une arborescence hyperquaternaire aléatoire à \(d\) dimensions (random \(d\)-dimensional quadtree) de \(n\) nœuds, ait \(k\) enfants. Il est bien connu que, pour \(k\) et \(d\) fixés, l'espérance \(e_{n,k,d}\) du nombre de nœuds ayant \(k\) enfants dans une telle arborescence satisfait le schéma de récurrence \[ e_{n,k,d} = p_{n,k,d} + 2^ d \sum^{n - 1}_{i = 0} \pi_{n,i,d} e_{i,k,d}, \] où \(p_{n,k,d}\) désigne la probabilité que la racine ait \(k\) enfants \((0 \leq k \leq 2^ d)\). Le présent travail contient une étude combinatoire et analytique de ces probabilités fondamentales \(p_{n,k,d}\). Elles sont d'abord représentées par des intégrales multiples classifiées à l'aide d'actions du groupe hyperoctaédral \(B_ d\) et une technique, basée sur la méthode de Laplace, pour leur calculus asymptotique \((n \to \infty)\) est ensuite présentée.
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 773914
zbMATH Keywords: multidimensional quadtrees
zbMATH Keywords: asymptotic analysis
describes a project that uses: Maple
MaRDI profile type: Publication
cites work: Q4002478
cites work: An Analysis of Randomd-Dimensional Quad Trees
cites work: Quad trees: A data structure for retrieval by composite keys
cites work: Analytic variations on quadtrees
cites work: Q4040797
cites work: Q4156973
cites work: Page usage in a quadtree index
cites work: Une nouvelle demonstration combinatoire des formules d'inversion de Lagrange
cites work: Combinatorial variations on multidimensional quadtrees
cites work: Q3767624
cites work: Q3916824
cites work: The Expected Distribution of Degrees in Random Binary Search Trees
description: scientific article; zbMATH DE number 773914