Partial Match Queries in Random k-d Trees

Authors:
  • HCHua-Huai Chern
    Hua-Huai Chern
  • HHHsien-Kuei Hwang
    Hsien-Kuei Hwang

Abstract
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.

This publication has 20 references indexed in Scilit: