Algorithm for finding all k-nearest neighbours in three-dimensional scattered points and its application in reverse engineering

Research output: Contribution to journalArticle


Colleges, School and Institutes


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.


Original languageEnglish
Pages (from-to)1467-1472
Number of pages6
JournalProceedings of the Institution of Mechanical Engineers Part B Journal of Engineering Manufacture
Issue number9
Publication statusPublished - 1 Jan 2007


  • reverse engineering, three-dimensional scattered point data, k-nearest neighbours