Relativ grannskapsgraf

Den relativa grannskapsgrafen med 100 slumpmässiga punkter i en kvadratisk enhet.

I beräkningsgeometri är den relativa grannskapsgrafen (RNG ) en oriktad graf som definieras på en uppsättning punkter i det euklidiska planet genom att koppla två punkter $p$ och $q$ med en kant när det inte existerar en tredje punkt $r$ som är närmare både $p$ och $q$ än de är varandra. Denna graf föreslogs av Godfried Toussaint 1980 som ett sätt att definiera en struktur från en uppsättning punkter som skulle matcha mänskliga uppfattningar om formen på uppsättningen.

Algoritmer

Supowit (1983) visade hur man konstruerar den relativa grannskapsgrafen för $n$ punkter i planet effektivt i $O(n\log n)$ tid. Det kan beräknas i $O(n)$ förväntad tid , för slumpmässig uppsättning punkter fördelade enhetligt i enhetskvadraten . Den relativa grannskapsgrafen kan beräknas i linjär tid från Delaunay-trianguleringen av punktuppsättningen.

Generaliseringar

Eftersom den endast definieras i termer av avstånden mellan punkter, kan den relativa grannskapsgrafen definieras för punktuppsättningar i vilken dimension som helst och för icke-euklidiska mått. Att beräkna den relativa grannskapsgrafen, för högre dimensionella punktuppsättningar, kan göras i tiden $O(n^{2})$ .

Relaterade grafer

relativa grannskapsgrafen är ett exempel på ett linsbaserat betaskelett . Det är en subgraf av Delaunay-trianguleringen . I sin tur euklidiska minimumspännande trädet en subgraf av det, av vilket det följer att det är en sammankopplad graf .

Urquhart -grafen , grafen som bildas genom att ta bort den längsta kanten från varje triangel i Delaunay-trianguleringen, föreslogs ursprungligen som en snabb metod för att beräkna den relativa grannskapsgrafen. Även om Urquhart-grafen ibland skiljer sig från den relativa grannskapsgrafen kan den användas som en approximation till den relativa grannskapsgrafen.