Computing point correspondences

The time complexity of the algorithm described above is dominated by the time for determining the closest points (brute force search ${\cal O}(n^2)$ for 3D scans of $n$ points). Several enhancements have been proposed [6,7,24]. We have implemented $k$d-trees as proposed by Simon et al. Fig. shows two slices taken from a $k$d-tree.

Figure: A $k$d-tree of scanned 3D data ($k=3$) of Fig. (top) first/black 3D scan. Two $(x,y)$-projections of slices at depths $z=100$ cm (a) and $z=550$ cm (b) are given.

(a)  (b)