Naar inhoud springen

Relative neighborhood graph

Uit Wikipedia, de vrije encyclopedie
Relative neighborhood graph van 100 punten

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

Als de afstand is tussen en , betekent dit dat en relatieve buren zijn dan en slechts dan als:

voor alle in verschillend van en .

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

Godfried Toussaint introduceerde het begrip in 1980 als hulpmiddel voor patroonherkenning.[1] Met de zouden structuren in een verzameling punten naar voor komen die overeenkomen met wat mensen erin zien.

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

Andere grafen

[bewerken | brontekst bewerken]

De euclidische minimaal opspannende boom van is de minimaal opspannende boom van de volledige graaf van , waarbij de afstand tussen alle knopen de euclidische afstand is. Er geldt dat een deelgraaf is van en op zijn beurt dat een deelgraaf is van de delaunay-triangulatie van :

De kan in lineaire tijd uit de delaunay-triangulatie worden berekend.[2]

De gabrielgraaf is een graaf die het begrip 'naburig' op een andere manier definieert. .

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

De nearest neighbor graph is de eenvoudigste van deze soort grafen. Daarin is ieder punt met zijn dichtstbijzijnde buur verbonden.

De is in het algemeen een onsamenhangende, gerichte graaf. De en de andere grafen zijn samenhangende, niet gerichte grafen. Men noemt deze hiërarchie weleens de toussainthiërarchie.[3]