Nearest neighbor graph

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 $\mathrm {NN} (x_{i})$.

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

De meest nabije buur (nearest neighbor) $\mathrm {NN} (x_{i})$ van een punt $x_{i}$ is het punt $x_{j}$, met $j\neq 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).
• Als 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{,}31\,n$.

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