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.