An Efficient Algorithm for the Nearest Neighbourhood Search for Point Clouds

Date Added: Sep 2011
Format: PDF

This paper presents a high-performance method for the k-nearest neighbourhood search. Starting from a point cloud, first the method carries out the space division by the typical cubic grid partition of the bounding box; then a new data structure is constructed. Based on these two previous steps, an efficient implementation of the k-nearest neighbourhood is proposed. The performance of the method here presented is compared with that of the kd-tree and bd-tree algorithms taken from the ANN library as regards the computing time for some benchmarking point clouds and artificially generated test cases. The results are analyzed and critically discussed.