Phase changes in random point quadtrees
Authors:
Open Access
- 1 May 2007
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 3 (2)
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.Keywords
This publication has 37 references indexed in Scilit:
- m‐ary Search trees when m ≥ 27: A strong asymptotics for the space requirementsRandom Structures & Algorithms, 2004
- Phase transition in a random fragmentation problem with applications to computer scienceJournal of Physics A: General Physics, 2002
- An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithmsJournal of Algorithms, 2002
- Limit laws for partial match queries in quadtreesThe Annals of Applied Probability, 2001
- On Convergence Rates in the Central Limit Theorems for Combinatorial StructuresEuropean Journal of Combinatorics, 1998
- Patterns in random binary search treesRandom Structures & Algorithms, 1997
- Mellin transforms and asymptotics: Finite differences and Rice's integralsTheoretical Computer Science, 1995
- Combinatorial variations on multidimensional quadtreesJournal of Combinatorial Theory, Series A, 1995
- Analytic variations on quadtreesAlgorithmica, 1993
- Page usage in a quadtree indexBIT Numerical Mathematics, 1992