Partial Match Queries in Random k-d Trees
Hua‐Huai Chern, Hsien‐Kuei Hwang · SIAM Journal on Computing · 2006
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.