Abstract: A spatial sphere algorithm is proposed for searching K- Nearest Neighbors (K-NN) of one measured point in scattered point set. At first, the scattered points are divided into a set of uniform cells. Suppose there exist a series of spatial spheres with the same center being the current point, and the radii being the distances from the point to one of the six cells planes respectively. A sphere with the smallest radius is first taken to determine the cells that interfere spatially with the sphere. Then a K-NN search is carried out within the interfering grids until the searching termination condition is satisfied. Otherwise, the sphere with larger radius is taken, and above searching process is repeated. Experiments show that the algorithm is very fast to search K-NN of scattered points in comparison with existing algorithms.

Key words: K-nearest neighbor, massive scattered points, reverse engineering, spatial partition