![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/e/e7/Relative_neighborhood_graph.svg/langnl-640px-Relative_neighborhood_graph.svg.png&w=640&q=50)
Relative neighborhood graph
Uit Wikipedia, de vrije encyclopedia
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.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e7/Relative_neighborhood_graph.svg/320px-Relative_neighborhood_graph.svg.png)
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.