Abstract
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.
| Original language | English |
|---|---|
| Article number | 1240235 |
| Journal | ACM Transactions on Algorithms |
| Volume | 3 |
| Issue number | 2 |
| DOIs | |
| State | Published - 1 May 2007 |
Keywords
- Analysis in distribution of algorithms
- Asymptotic transfer
- Central limit theorems
- Depth
- Differential equations
- Grid trees
- Local limit theorems
- Mellin transforms
- Page usage
- Phase transitions
- Quadtrees
- Total path length
Fingerprint Dive into the research topics of 'Phase changes in random point quadtrees'. Together they form a unique fingerprint.
Cite this
Chern, H. H., Fuchs, M., & Hwang, H. K. (2007). Phase changes in random point quadtrees. ACM Transactions on Algorithms, 3(2), [1240235]. https://doi.org/10.1145/1240233.1240235