Nearest neighbor graph

De (niet-gerichte) nearest neighor graph van 100 punten in het Euclidische vlak

De nearest neighbor graph (NNG) van een verzameling punten in de Euclidische ruimte is de gerichte graaf waarin vanuit elk punt x_i een kant vertrekt naar zijn meest nabije buur NN(x_i).

De meest nabije buur (nearest neighbor) NN(x_i) van een punt x_i is het punt x_j, met j verschillend van i, waarvoor de afstand d(x_i, x_j) minimaal is.

Het is mogelijk dat er meerdere punten op dezelfde minimale afstand van x_i liggen; in dat geval kiest men als de meest nabije buur het punt met de hoogste index.

De relatie "x is de naaste buur van y" is niet symmetrisch, vandaar dat de NNG een gerichte graaf is.

Eigenschappen

• Voor een verzameling punten in het Euclidische vlak is de NNG een planaire graaf. De hoek tussen twee kanten die in een punt toekomen is ten minste 60°. Er kunnen dus hoogstens zes kanten in een punt toekomen; anders gezegd: de graad van een punt is hoogstens zes.
• Langs elk gericht pad in een NNG hebben de opeenvolgende kanten een niet-stijgende lengte.
• De enige cykels in de NNG zijn 2-cykels (punt a is de NN van punt b en vice versa).
• Wanneer de NNG wordt herleid tot een niet-gerichte graaf (waarbij de 2-cykels vervangen worden door één kant tussen de twee punten) is de NNG een subgraaf van de Delaunay-triangulatie van de verzameling punten en van de minimaal opspannende boom.
• In het algemeen is de NNG een niet-samenhangende graaf, een "woud" van deelgrafen van de minimaal opspannende boom die "puntenclusters" verbinden. Voor een verzameling van n uniform verdeelde, willekeurig gekozen punten in het eenheidsvierkant is het aantal deelgrafen van de NNG asymptotisch gelijk aan ongeveer 0,31n.

Uitbreiding

De k-nearest neighbor graph (k-NNG) is een gerichte graaf waarin elk punt x_i verbonden is met de k meest nabije buren. k kan gaan van 1 tot n-1 (als n het totaal aantal punten in de verzameling is). De NNG is een speciaal geval van de k-NNG, namelijk voor k=1.

Toepassingen

Het bepalen van de NNG of k-NNG vindt toepassing in onder meer de computationele meetkunde, computergraphics, patroonherkenning en geografische informatiesystemen.

Bronnen, noten en/of referenties