ABSTRACT
Strengths: The expected depth of a k-dimensional extension of a quad tree is a multiplicative factor of k less than a k-d tree (Chapter 47), since the branching factor is 2k at each level of the tree. So for uniformly distributed points, a quad tree has 3 times fewer nodes than a 2d-tree, and 9 times fewer nodes than a 3d-tree. A quad tree (for k = 2) or an oct tree (for k = 3) leads to faster search times, especially if up to 3 comparisons can be made in parallel. Even when the comparisons are made sequentially, the number of references to follow is reduced by a factor of k when using a k-dimensional extension of a quad tree.
