Time Complexity Reduction

The ICP algorithms spends most of its time in creating the point pairs. $k$D-trees (here $k=3$) have been suggested for speed up the data access[1]. They are a binary tree with terminal buckets. The data is stored in the buckets, the keys are selected, such that a data space is divided into two equal parts. This ensures that a data point can be selected in $O(\log n)$ at average.

Recently, Greenspan and Yurick have introduced approximate $k$d-trees (Apr-$k$d-tree)[4]. The idea behind this is to return as an approximate nearest neighbor $\V p_a$ the closest point $\V p_b$ in the bucket region where the given point $\V p$ lies. This value is determined from the depth-first search, thus expensive Ball-Within-Bounds tests and backtracking are not necessary[4]. In addition to these ideas we avoid the linear search within the bucket. During the computation of the Apr-$k$d-tree the mean values of the points within a bucket are computed and stored. Then the mean value of the bucket is used as the approximate nearest neighbor, replacing the linear search. Table 1 summarizes the results.

Table 1. Computing time and number of ICP iterations to align two 3D reliefs (Pentium-IV-2400).

point pairing method	time	# ICP iterations
brute force search	4 h 25 min	87
$k$D-tree	14.2 sec	87
Apx-$k$D-tree	10.9 sec	85