Algorithm for Finding k-Nearest Neighbors of Scattered Points in Three Dimensions

A new and simple algorithm is presented.At first,the min-max box of the data set is divided into a set of uniform grids,and then the indexes of points are sorted into appropriate cell for finding nearest neighbors.A method of estimating the size of grid is introduced by overall considering the range of data set,the total numbers of points and the numbers of nearest neighbors.Simulated experiments showed that it is very easy to obtain the size of grids for a nearly optimal searching speed.