| Abstract | The kd-tree is a popular and simple data structure for range searching and nearest neighborsearching. Such a tree subdivides space into rectangular cells through the recursive application
of some splitting rule. The choice of splitting rule affects the shape of cells and the structure
of the resulting tree. It has been shown that an important element in achieving efficient query
times for approximate queries is that each cell should be fat, meaning that the ratio of its longest
side to shortest side (its aspect ratio) should be bounded. Subdivisions with fat cells satisfy a
property called the packing constraint, which bounds the number of disjoint cells of a given size
that can overlap a ball of a given radius. We consider a splitting rule called the sliding-midpoint
rule. It has been shown to provide efficient search times for approximate nearest neighbor and
range searching, both in practice and in terms of expected case query time. However it has not
been possible to prove results about this tree because it can produce cells of unbounded aspect
ratio. We show that in spite of this, the sliding-midpoint rule generates subdivisions that satisfy
the packing constraint, thus explaining their good performance.
|
