A major open problem for the analysis of partial-match queries in random quadtrees is the determination of the leading constants of the expected cost. More precisely, it is known (see [FGPR93]) that the expected cost, say , of a random partial-match query in a random quadtree of keys (chosen uniformly i.i.d. from the hypercube ) satisfies , where is the zero of the indicial equation with the largest real part, being the number of specified coordinates in the random query. But the exact value of is unknown for . We propose a means of deriving expressions for . The approach is based on extending our recent tools for Cauchy-Euler equations. In the special cases when only one coordinate is specified or unspecified, the constant or can be computed in a more explicit way in terms of hypergeometric functions. Our approach is also applicable to k-d trees.
Back to the Index