We propose an analytic approach for the average-case analysis of (random) partial match queries in random k-d trees. We use a more straightforward analysis based on a single differential equation instead of the linear system used by Flajolet and Puech [FP86]. Then our theory for "perturbed" Cauchy-Euler differential equations can be applied to derive the required asymptotics, with analytic expressions for the leading constants. The leading constants can in some special cases be expressed more explicitly in terms of known (like Gamma or hypergeometric) functions.
Back to the Index