Relative neighborhood graph

Relative neighborhood graph van 100 punten

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.

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)\le \mathrm{m}\mathrm{a}\mathrm{x}\{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{R}\mathrm{N}\mathrm{G}$ in 1980 als hulpmiddel voor patroonherkenning. Met de $\mathrm{R}\mathrm{N}\mathrm{G}$ zouden structuren in een verzameling punten naar voor komen die overeenkomen met wat mensen erin zien.

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

Andere grafen

De euclidische minimaal opspannende boom $\mathrm{M}\mathrm{O}\mathrm{B}$ 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{M}\mathrm{O}\mathrm{B}(S)$ een deelgraaf is van $\mathrm{R}\mathrm{N}\mathrm{G}(S)$ en op zijn beurt dat $\mathrm{R}\mathrm{N}\mathrm{G}(S)$ een deelgraaf is van de delaunay-triangulatie $\mathrm{D}\mathrm{T}(S)$ van $S$:

$\mathrm{M}\mathrm{O}\mathrm{B}(S)\subseteq \mathrm{R}\mathrm{N}\mathrm{G}(S)\subseteq \mathrm{D}\mathrm{T}(S)$

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

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

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

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

$\mathrm{N}\mathrm{N}\mathrm{G}(S)\subseteq \mathrm{M}\mathrm{O}\mathrm{B}(S)\subseteq \mathrm{R}\mathrm{N}\mathrm{G}(S)\subseteq \mathrm{U}\mathrm{G}(S)\subseteq \mathrm{G}\mathrm{G}(S)\subseteq \mathrm{D}\mathrm{T}(S)$

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