The optimized $k$d-tree

The objective of optimizing $k$d-trees is to reduce the expected number of visited leafs. Three parameters are adjustable, namely, the direction and place of the split axis as well as the number of points in the buckets. Splitting the point set at the median ensures that every $k$d-tree entry has the same probability [11]. The median can be found in linear time, thus the time complexity for constructing the tree is not affected. Furthermore, the split axis should be oriented perpendicular to the longest axis to minimize the amount of backtracking (see Fig. ). Friedman and collegues prove that a bucket size of 1 is optimal [11]. Nevertheless, in practice it turned out that a slightly larger bucket size is faster as given in Fig. .

Figure: Computing time in millseconds for a 3D scan matching dependend on the bucket size of a $k$d- and bd-tree.