relative neighborhood graph

De relative neighborhood graph (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.