An algorithm of search of nearest neighbors leading to average computing time per point independent of the total number of points

Abstract : A new algorithm of search of nearest neighbors is proposed. It is based upon the partition of the vorking domain in cells. It presents two major characteristics. First, the average number of distance calculations can be done as small as required. Secondly, the average computing time per point is indépendant of the total number of points to be classified. The theoretical behavior has been studied for a uniform distribution in a plan. Experimental verifications are provided.