Partial match queries in random k-d trees
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.
partial match queries k-d trees differential equations average-case analysis of algorithms method of linear operators asymptotic analysis