Since the ICP algorithm, and therefore our 6D SLAM method, extensively computes nearest neigbours, approximating the nearest neigbours will speed up the algorithm. S. Arya and D. Mount introduce the following notion for approximating the nearest neighbor [3]: Given an , then the point is the -approximate nearest neighbour of the point , iff

where denotes the true nearest neighbour, i.e., has a maximal distance of to the true nearest neighbour. Using this notation in every step the algorithm records the closest point . The search terminates if the distance to the unanalyzed leaves is larger than

root 2005-05-03