Refined asymptotics for the number of leaves of random point quadtrees

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

研究成果: Conference contribution同行評審

1 引文 斯高帕斯(Scopus)

摘要

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.

原文English
主出版物標題29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2018
編輯Mark Daniel Ward, James Allen Fill
發行者Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN(電子)9783959770781
DOIs
出版狀態Published - 1 六月 2018
事件29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2018 - Uppsala, Sweden
持續時間: 25 六月 201829 六月 2018

出版系列

名字Leibniz International Proceedings in Informatics, LIPIcs
110
ISSN(列印)1868-8969

Conference

Conference29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2018
國家Sweden
城市Uppsala
期間25/06/1829/06/18

引用此