# 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.
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.
* ↑ GT Toussaint. The relative neighborhood graph of a finite planar set, 1980. in Pattern Recognition, 12, blz 261–268
* ↑ A Lingas. A linear-time construction of the relative neighborhood graph from the Delaunay triangulation, 1994. in Computational Geometry, 4, 4, blz 199-208 DOI:10.1016/0925-7721(94)90018-3
* ↑ A Adamatzky. Does the plasmodium follow the Toussaint hierarchy?, 2010. hoofdstuk 6 in A Adamatzky. Physarum Machines: Computers from Slime Mould, ISBN 9789814327589