Name
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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1145/1240233.1240235 | ACM Transactions on Algorithms (TALG) |
Keywords | Field | DocType |
fixed limit law,page usage,grid trees,random d-dimensional point quadtrees,search tree,asymptotic transfer,phase transitions,local limit theorems,depth,analysis in distribution of algorithms,additional phase change,random point quadtrees,local limit theorem,brief discussion,m-ary search tree,mellin transforms,quadtrees,central limit theorems,limit law,convergence rate,total path length,differential equations,stronger approximation result,phase transition,central limit theorem,mellin transform,differential equation,limit laws,phase change | Convergence (routing),Limit of a function,Discrete mathematics,Differential equation,Combinatorics,Phase transition,Cost Measures,Grid,Mathematics | Journal |
Volume | Issue | ISSN |
3 | 2 | 1549-6325 |
Citations | PageRank | References |
7 | 0.59 | 29 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hua-Huai Chern | 1 | 78 | 7.25 |
| Michael Fuchs | 2 | 52 | 8.98 |
| Hsien-Kuei Hwang | 3 | 365 | 38.02 |