Refined asymptotics for the number of leaves of random point quadtrees

DOI10.4230/LIPICS.AOFA.2018.23MaRDI QIDQ4993545zbMATH OpenFDO

Authors Michael Fuchs, Noela Müller, Henning Sulzbach

Publication date 15 June 2021

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)

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

Cites work

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

Cited in

(2)

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

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)