• Media type: Text; E-Article; Electronic Conference Proceeding
  • Title: Refined Asymptotics for the Number of Leaves of Random Point Quadtrees
  • Contributor: Fuchs, Michael [Author]; Müller, Noela S. [Author]; Sulzbach, Henning [Author]
  • Published: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018
  • Language: English
  • DOI: https://doi.org/10.4230/LIPIcs.AofA.2018.23
  • Keywords: stochastic fixed-point equation ; contraction method ; Quadtree ; central limit theorem ; number of leaves ; positivity of variance ; phase change
  • Origination:
  • Footnote: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Description: 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.
  • Access State: Open Access