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.

We solve the open problem of characterizing the leading constant in the asymptotic approximation to the expected cost used for random partial match queries in random k-d trees. Our approach is new and of some generality; in particular, it is applicable to many problems involving differential equations (or difference equations) with polynomial coefficients.

We propose a simple direct approach for computing the expected cost of random partial match queries in random quadtrees. This approach gives not only an explicit expression for the leading constant in the asymptotic approximation of the expected cost but also more terms in the asymptotic expansion if desired.