2026-08-17T17:24:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8916 2024-03-06T10:43:44Z ddc:004 open_access

Refined Asymptotics for the Number of Leaves of Random Point Quadtrees Fuchs, Michael Müller, Noela S. Sulzbach, Henning Quadtree number of leaves phase change stochastic fixed-point equation central limit theorem positivity of variance contraction method In the early 2000s, several phase change results from distributional convergence to distributional non-convergence have been obtained for shape parameters of random discrete structures. Recently, for those random structures which admit a natural martingale process, these results have been considerably improved by obtaining refined asymptotics for the limit behavior. In this work, we propose a new approach which is also applicable to random discrete structures which do not admit a natural martingale process. As an example, we obtain refined asymptotics for the number of leaves in random point quadtrees. More applications, for example to shape parameters in generalized m-ary search trees and random gridtrees, will be discussed in the journal version of this extended abstract. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Fuchs and Noela S. Müller and Henning Sulzbach 2018 Is Part Of LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2018.23 urn:nbn:de:0030-drops-89165 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.23 eng https://creativecommons.org/licenses/by/3.0/legalcode