| Abstract | Algorithms that use point-cloud models make heavy use of the neighborhoods of the points. These neighborhoodsare used to compute the surface normals for each point, mollification, and noise removal. All of these primitive
operations require the seemingly repetitive process of finding the k nearest neighbors of each point. These algo-
rithms are primarily designed to run in main memory. However, rapid advances in scanning technologies have
made available point-cloud models that are too large to fit in the main memory of a computer. This calls for more
efficient methods of computing the k nearest neighbors of a large collection of points many of which are already in
close proximity. A fast k nearest neighbor algorithm is presented that makes use of the locality of successive points
whose k nearest neighbors are sought to significantly reduce the time needed to compute the neighborhood needed
for the primitive operation as well as enable it to operate in an environment where the data is on disk. Results
of experiments demonstrate an order of magnitude improvement in the time to perform the algorithm and several
orders of magnitude improvement in work efficiency when compared with several prominent existing method.
|
