A fast and exact algorithm for computing the k-nearest neighbours, or k-closest points in terms of Euclidean distance, for all data in three-dimensional point clouds is presented that avoids using complicated Voronoi diagrams or Dirichlet tessellations. Experimental evidence suggests that the algorithm has a timing of O(n) for most practical values of k under the condition: k < 0.05n, where n is the number of three-dimensional points in the cloud. Case studies are presented to illustrate the robustness and efficiency of the method and a comparison is made to an existing exact method.
ZhangB.SrihariS.Fast k-nearest neighbor classification using cluster based treeIEEE Trans. Pattern Analysis Mach. Intell., 2004, 26(4), 525–528.
9.
EdelsbrunnerH.Algorithms in combinatorial geometry, 1987 (Springer-Verlag, New York).
10.
GoodsellG.On finding p-th nearest neighbours of scattered points in two dimensions for smallp. Computer Aided Geometric Des., 2000, 17, 387–392.
11.
PieglL.TillerW.Algorithm for finding all k nearest neighborsComputer-Aided Des., 2002, 34, 167–172.
12.
CrippsR.LiX.Data segmentation using implicit surfaces. In HindujaS., (Ed.), Proceedings of the 34th MATADOR Conference. UMIST, 2004, pp. 75–80.
13.
LiX.Geometric property estimation and segmentation in reverse engineering. PhD Thesis, University of Birmingham, 2004.
14.
DeyT.BajajC.SugiharaK.On good triangulation in three dimensions. In Proceedings of the ACM Symposium on Solid modelling and application, 1991 (ACM Press, New York), pp. 431–441.
15.
16.
SarkarM.LeongT.Application of k-nearest neighbors algorithm on breast cancer diagnosis problem. In Proceedings of the 2000 AMIA Annual Symposium, L.A., 2000.
17.
Dataset 4 kindly supplied by Ralph Martin, Department of Computer Science, University of Cardiff, Cardiff, Wales, CF24 3AA, UK.
