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

Claude Delannoy (1, 2)

1 CRPE - Centre de recherches en physique de l'environnement terrestre et planétaire
2 LPCE - Laboratoire de physique et chimie de l'environnement

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.

Domaines: Sciences de la Terre

Claude Delannoy. An algorithm of search of nearest neighbors leading to average computing time per point independent of the total number of points. [Research Report] Note technique CRPE n° 36, Centre de recherches en physique de l'environnement terrestre et planétaire (CRPE). 1976, 22 p., graphiques. ⟨hal-02191377⟩