Relative neighborhood graph

De relative neighborhood graph, afgekort RNG, van een verzameling $S$ van punten in het euclidische vlak is een graaf waarin twee punten $p$ en $q$ verbonden zijn door een zijde als er geen enkel ander punt in $S$ dichter bij $p$ en $q$ ligt dan $p$ en $q$ zelf. $p$ en $q$ zijn dan 'relatieve buren' van elkaar.

Relative neighborhood graph van 100 punten

Als $d(p,q)$ de afstand is tussen $p$ en $q$, betekent dit dat $p$ en $q$ relatieve buren zijn dan en slechts dan als:

$d(p,q)\leq \mathrm {max} \{d(p,r),d(q,r)\}$ voor alle $r$ in $S$ verschillend van $p$ en $q$.

In meetkundige zin kan men deze eis als volgt interpreteren: teken een cirkel met straal gelijk aan de afstand $d(p,q)$ en middelpunt $p$. Teken een tweede cirkel met zelfde straal en middelpunt $q$. De lensvormige doorsnede van beide cirkels is de verzameling punten die dichter bij $p$ en $q$ liggen dan de afstand $d(p,q)$. Deze doorsnede mag geen punten van $S$ bevatten.

Godfried Toussaint introduceerde het begrip $\mathrm {RNG}$ in 1980 als hulpmiddel voor patroonherkenning. Met de $\mathrm {RNG}$ zouden structuren in een verzameling punten naar voor komen die overeenkomen met wat mensen erin zien.

Omdat het begrip $\mathrm {RNG}$ alleen met behulp van de afstand tussen punten is gedefinieerd, kan de $\mathrm {RNG}$ ook voor puntenverzamelingen in meer dimensies en in een niet-euclidische meetkunde worden gedefinieerd.

Andere grafen

De euclidische minimaal opspannende boom $\mathrm {MOB}$ van $S$ is de minimaal opspannende boom van de volledige graaf van $S$, waarbij de afstand tussen alle knopen de euclidische afstand is. Er geldt dat $\mathrm {MOB} (S)$ een deelgraaf is van $\mathrm {RNG} (S)$ en op zijn beurt dat $\mathrm {RNG} (S)$ een deelgraaf is van de delaunay-triangulatie $\mathrm {DT} (S)$ van $S$:

$\mathrm {MOB} (S)\subseteq \mathrm {RNG} (S)\subseteq \mathrm {DT} (S)$

De $\mathrm {RNG} (S)$ kan in lineaire tijd uit de delaunay-triangulatie worden berekend.

De gabrielgraaf $\mathrm {GG}$ is een graaf die het begrip 'naburig' op een andere manier definieert. $\mathrm {RNG} (S)\subseteq \mathrm {GG} (S)$.

De urquhartgraaf $\mathrm {UG}$ ontstaat door de langste zijde in iedere driehoek van de delaunay-triangulatie te verwijderen. Er werd eerst gedacht dat deze graaf gelijk aan $\mathrm {RNG} (S)$ was, maar nadien is bewezen dat de $\mathrm {UG} (S)$ soms groter is dan de $\mathrm {RNG} (S)$. De $\mathrm {UG} (S)$ kan wel gebruikt worden als goede benadering van $\mathrm {RNG} (S)$.

De nearest neighbor graph $\mathrm {NNG}$ is de eenvoudigste van deze soort grafen. Daarin is ieder punt met zijn dichtstbijzijnde buur verbonden.

$\mathrm {NNG} (S)\subseteq \mathrm {MOB} (S)\subseteq \mathrm {RNG} (S)\subseteq \mathrm {UG} (S)\subseteq \mathrm {GG} (S)\subseteq \mathrm {DT} (S)$

De $\mathrm {NNG}$ is in het algemeen een onsamenhangende, gerichte graaf. De $\mathrm {MOB}$ en de andere grafen zijn samenhangende, niet gerichte grafen. Men noemt deze hiërarchie weleens de toussainthiërarchie.

Voetnoten