Refined asymptotics for the number of leaves of random point quadtrees

Michael Fuchs, Noela S. Müller, Henning Sulzbach

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish
Title of host publication29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2018
EditorsMark Daniel Ward, James Allen Fill
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770781
DOIs
StatePublished - 1 Jun 2018
Event29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2018 - Uppsala, Sweden
Duration: 25 Jun 201829 Jun 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume110
ISSN (Print)1868-8969

Conference

Conference29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2018
CountrySweden
CityUppsala
Period25/06/1829/06/18

Keywords

  • Central limit theorem
  • Contraction method
  • Number of leaves
  • Phase change
  • Positivity of variance
  • Quadtree
  • Stochastic fixed-point equation

Cite this

Fuchs, M., Müller, N. S., & Sulzbach, H. (2018). Refined asymptotics for the number of leaves of random point quadtrees. In M. D. Ward, & J. A. Fill (Eds.), 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2018 [23] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 110). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.AofA.2018.23