__Maximum-Spread k-d Trees__

__Maximum-Spread k-d Trees__

One very popular class of BSP tree is the *k*-d tree, see Chapter 16. Although there are very few theoretical bounds known on these structures, there is a lot of empirical evidence that shows them to be extremely eﬃcient for numerous geometric applications. In particular, one variant the maximum-spread *k*-d tree has long been considered an ideal *k*-d tree. Given a set of points *S *and a particular axis dimension *x**d*, deﬁne the *spread *of *S *in *x**d *to be the diﬀerence between the minimum and maximum coordinates of the points in that dimension. The maximum-spread *k*-d tree is formed by choosing at each internal node a cutting plane orthogonal to the axis of maximum spread placed at the median point in this direction, see for example [16]. Arya *e**t al. *[1] applied the maximum-spread *k*-d tree to their approximate nearest-neighbor searching algorithm and experimentally showed that they were comparable to the theoretically eﬃcient BBD tree. Later Dickerson *e**t al. *[9, 11] proved the following theorem regarding maximum-spread *k*-d trees, referred to there as longest-side *k*-d trees:

*TH**EOREM 26.8 **Suppose we are given a maximum-spread **k**-d tree **T **c**o**nstructed on a** **se**t **S **o**f **n **p**oi**nts in *IR*d**. Then the packing function **ρ*(*n*) *o**f **T **fo**r a region annulus **A **is **O*(log*d**−*1 *n*)*. That is, the class of maximum-spread **k**-d trees is an **O*(log*d**−*1 *n*)*-quasi-BAR **tree.*

Although the bound is not as good as for BBD trees and BAR trees, the simplicity of the structure yields low constant factors and explains why in practice these trees perform so well. Experimental comparisons to BBD trees and BAR trees veriﬁed this result and showed that only for very highly clustered data did the dependency on log*d**−*1 *n *become prominent [1, 11].

In practice, unless data is highly clustered and the dimension is moderately large, the maximal-spread *k*-d tree is an ideal structure to use. However, for such data sets both the BBD tree and the BAR tree revert to the same behavior as the maximal-spread tree, and they perform well even with highly clustered data. Because of its simpler structure, the BBD tree is potentially more practical than the BAR tree.