Refined asymptotics for the number of leaves of random point quadtrees

DOI10.4230/LIPICS.AOFA.2018.23zbMATH Open1478.68063MaRDI QIDQ4993545FDOQ4993545

Authors: Michael Fuchs, Noela Müller, Henning Sulzbach 

Publication date: 15 June 2021

Recommendations

• Phase changes in random point quadtrees
• Strong convergence of partial match queries in random quadtrees
• Phase changes in random \(m\)-ary search trees and generalized quicksort
• Asymptotic fringe distributions for general families of random trees
• Around the root of random multidimensional quadtrees

zbMATH Keywords

central limit theoremquadtreephase changecontraction methodstochastic fixed-point equationnumber of leavespositivity of variance

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Data structures (68P05) Combinatorial probability (60C05)

Cites Work

• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• Functional limit theorems for multitype branching processes and generalized Pólya urns.
• Limit laws for local counters in random binary search trees
• Phase changes in random point quadtrees
• Hypergeometrics and the cost structure of quadtrees
• m‐ary Search trees when m ≥ 27: A strong asymptotics for the space requirements
• Analysis of the space of search trees under the random insertion algorithm
• The Joint Distribution of Elastic Buckets in Multiway Search Trees
• Phase changes in random \(m\)-ary search trees and generalized quicksort
• Title not available (Why is that?)
• Refined quicksort asymptotics
• The CLT Analogue for Cyclic Urns
• A note on the quicksort asymptotics
• Dependence and phase changes in random m‐ary search trees

Cited In (2)

• Local limit of labeled trees and expected volume growth in a random quadrangulation
• Correction to the leading term of asymptotics in the problem of counting the number of points moving on a metric tree

This page was built for publication: Refined asymptotics for the number of leaves of random point quadtrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993545)