The objective of optimizing k-d trees is to reduce the expected number of visited leaves. Three parameters are adjustable, namely, the direction and position of the split axis as well as the maximal number of points in the buckets. Splitting the point set at the median ensures that every k-d tree entry has the same probability [7]. 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. 2). Friedman and colleagues prove that a bucket size of 1 is optimal [7]. Nevertheless, in practice it turned out that a slightly larger bucket size is faster [11].