Performance of cached k-d tree search

The proposed ICP variant uses exact closest point search. In contrast to the previously discussed approximate k-d tree search for ICP algorithms [10,17], registration inaccuracies or errors due to approximation cannot occur.

Friedman et al. prove that searching for closest points using k-d trees needs logarithmic time [7], i.e., the amount of backtracking is independent of the number of stored points in the tree. Since the ICP algorithm iterates the closest point search, the performance derives to ${\cal O}(I N_d \log N_m)$, with $I$ the number of iterations. Note: Brute-force ICP algorithms have a performance of ${\cal O}(I N_d N_m)$.

The proposed cached k-d tree search needs ${\cal O}((I + \log N_m) N_d)$ time in the best case. This performance is reached if constant time is needed for backtracking, resulting in $N_d\log N_m$ time for constructing the tree, and $I \cdot N_d$ for searching in case no backtracking is necessary. Obviously the backtracking time depends on the computed ICP transformation ( $\mathbf{R}, \mathbf{t}$). For small transformations the time is nearly constant.

Cached k-d tree search needs ${\cal O}(N_d)$ extra memory for the vector $\mathbf{v}$, i.e., for storing the pointers to the tree leaves. Furthermore, additional ${\cal O}(N_m)$ memory is needed for storing the backwards pointers in the k-d tree.