title: Relative neighborhood graph
text: 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. 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 
  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.
  
  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.
  
  Grafentheorie
  Meetkunde