In the early 2000s, several phase change results from distributional convergence to distributional non-convergence have been obtained for shape parameters of random discrete structures. Recently, for those random structures which admit a natural martingale process, these results have been considerably improved by obtaining refined asymptotics for the limit behavior. In this work, we propose a new approach which is also applicable to random discrete structures which do not admit a natural martingale process. As an example, we obtain refined asymptotics for the number of leaves in random point quadtrees. More applications, for example to shape parameters in generalized m-ary search trees and random gridtrees, will be discussed in the journal version of this extended abstract.

We consider the problem of recovering items matching a partially specified pattern in multidimensional trees (quad trees and k-d trees). We assume the traditional model where the data consist of independent and uniform points in the unit square. For this model, in a structure on n points, it is known that the number of nodes Cn (ξ) to visit in order to report the items matching an independent and uniformly on [0,1] random query ξ satisfies E[Cn(ξ)] ∼ κnβ, where κ and β are explicit constants. We develop an approach based on the analysis of the cost Cn (x) of any fixed query x ∊ [0, 1], and give precise estimates for the variance and limit distribution of the cost Cn (x). Our results permit to describe a limit process for the costs Cn(x) as x varies in [0, 1]; one of the consequences is that E[maxx∊[0, 1] Cn(x)] ∼ γnβ; this settles a question of Devroye [Pers. Comm., 2000].