Refined asymptotics for the number of leaves of random point quadtrees

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

Authors

Colleges, School and Institutes

External organisations

  • National Chiao Tung University Taiwan
  • Goethe-Universität Frankfurt Am Main

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.

Details

Original languageEnglish
Title of host publication29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2018
EditorsJames Allen Fill, Mark Daniel Ward
Publication statusPublished - 25 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 (Electronic)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

ASJC Scopus subject areas