Phase Changes in Random Point Quadtrees

檔案

本條目沒有附加檔案。

至出版者網站查看(DOI) ›

日期

2007-05-01

類型

期刊名稱

ACM TRANSACTIONS ON ALGORITHMS

卷期與頁次

第 3 卷第 2 期

ISSN

1549-6325

語言

英文

摘要

We show that a wide class of linear cost measures (such as the number of leaves) in random d-dimensional point quadtrees undergo a change in limit laws: If the dimension d = 1, ..., 8, then the limit law is normal; if d >= 9 then there is no convergence to a fixed limit law. Stronger approximation results such as convergence rates and local limit theorems are also derived for the number of leaves, additional phase changes being unveiled. Our approach is new and very general, and also applicable to other classes of search trees. A brief discussion of Devroye's grid trees (covering m-ary search trees and quadtrees as special cases) is given. We also propose an efficient numerical procedure for computing the constants involved to high precision.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Chern, H.-H., Fuchs, M., & Hwang, H.-K. (2007). Phase Changes in Random Point Quadtrees. ACM TRANSACTIONS ON ALGORITHMS, 3(2), 0. https://doi.org/10.1145/1240233.1240235

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/153230