Relativ grannskapsgraf

En relativ grannskapsgraf är en oriktad graf definierad på en uppsättning punkter i det euklidiska planet genom att koppla två punkter p och q med en kant när det inte finns någon tredje punkt r som är närmare både p och q än p och q är till var och en Övrig. Denna graf föreslogs av Godfried Toussaint 1980 som ett sätt att definiera en struktur på en uppsättning punkter som återspeglar människans uppfattning om formen på uppsättningen [1] [2] [3] .

Algoritmer

Supovit [4] visade hur man effektivt bygger en relativ grannskapsgraf i O( n  log  n ) tid [5] . Grafen kan beräknas i medeltid O ( n ) för en godtycklig uppsättning punkter likformigt fördelade i kvadraten [6] . Den relativa grannskapsgrafen kan beräknas i linjär tid från Delaunay-trianguleringen av en uppsättning punkter [7] [8] .

Generaliseringar

Eftersom en graf endast definieras i termer av avstånd mellan punkter, kan en relativ grannskapsgraf definieras för uppsättningar av punkter i ett utrymme av vilken dimension som helst [1] [9] och för icke-euklidiska mått [1] [7] [10 ] [11] .

Relaterade grafer

Den relativa grannskapsgrafen är ett exempel på en betakärna . Detta är en subgraf av Delaunay-trianguleringen . I sin tur är det euklidiska minimumspännande trädet dess subgraf, vilket antyder att det är en sammankopplad graf .

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

Anteckningar

1. ↑ 1 2 3 Jaromczyk, Kowaluk, 1991 , sid. 181–191.
2. ↑ Toussaint, 1980 , sid. 261–268.
3. ↑ Jaromczyk, Toussaint, 1992 , sid. 1502–1517
4. ↑ Supowit, 1983 .
5. ↑ Supowit, 1983 , sid. 428–448.
6. ↑ Katajainen, Nevalainen, Teuhola, 1987 , sid. 77–86.
7. ↑ 1 2 Jaromczyk, Kowaluk, 1987 , sid. 233–241.
8. ↑ Lingas, 1994 , sid. 199–208.
9. ↑ Agarwal, Matousek, 1992 , sid. 58–65.
10. ↑ O'Rourke, 1982 , sid. 189–192.
11. ↑ Lee, 1985 , sid. 327–332.
12. ↑ Urquhart, 1980 , sid. 556–557.
13. ↑ Toussaint, 1980 , sid. 860.
14. ↑ Andrade, de Figueiredo, 2001 .

Litteratur

• Toussaint GT Den relativa grannskapsgrafen för en finit plan uppsättning // Mönsterigenkänning. - 1980. - T. 12 , nr. 4 . — S. 261–268 . - doi : 10.1016/0031-3203(80)90066-7 .
• Jaromczyk JW, Toussaint GT Relativ grannskapsdiagram och deras släktingar // Proceedings of the IEEE. - 1992. - T. 80 , nr. 9 . - S. 1502-1517 . - doi : 10.1109/5.163414 .
• Supowit KJ Den relativa grannskapsgrafen, med en tillämpning på minsta spännträd // J. ACM . - 1983. - T. 30 , nr. 3 . — S. 428–448 . - doi : 10.1145/2402.322386 .
• Jyrki Katajainen, Olli Nevalainen, Jukka Teuhola. En linjär algoritm för förväntad tid för beräkning av plana relativa grannskapsgrafer // Information Processing Letters. - 1987. - T. 25 , nr. 2 . — s. 77–86 . - doi : 10.1016/0020-0190(87)90225-0 .
• Jaromczyk JW, Kowaluk M. En anteckning om relativa grannskapsgrafer // Proc. 3:e Symp. Beräkningsgeometri. - New York, NY, USA: ACM, 1987. - S. 233-241. doi : 10.1145 / 41958.41983 .
• Lingas A. En linjär-tidskonstruktion av den relativa grannskapsgrafen från Delaunay-trianguleringen // Computational Geometry. - 1994. - T. 4 , nr. 4 . — S. 199–208 . - doi : 10.1016/0925-7721(94)90018-3 .
• Jaromczyk JW, Kowaluk M. Konstruera den relativa grannskapsgrafen i 3-dimensionell euklidisk rymd // Discrete Appl. Math.. - 1991. - V. 31 , nr. 2 . — S. 181–191 . - doi : 10.1016/0166-218X(91)90069-9 .
• Pankaj K. Agarwal, Jiri Matousek. Relativa grannskapsgrafer i tre dimensioner // Proc. 3:e ACM–SIAM Symp. Diskreta algoritmer . - 1992. - S. 58-65.
• O'Rourke J. Beräknar den relativa grannskapsgrafen i L 1- och L ∞ -måtten // Mönsterigenkänning. - 1982. - T. 15 , nr. 3 . — S. 189–192 . - doi : 10.1016/0031-3203(82)90070-X .
• Lee DT Relativa grannskapsgrafer i L 1 -metriken // Mönsterigenkänning. - 1985. - T. 18 , nr. 5 . — S. 327–332 . - doi : 10.1016/0031-3203(85)90023-8 .
• Urquhart RB Algoritmer för beräkning av relativ grannskapsgraf // Elektronikbokstäver. - 1980. - T. 16 , nr. 14 . — S. 556–557 . - doi : 10.1049/el:19800386 .
• Toussaint GT Kommentar: Algoritmer för att beräkna relativ grannskapsgraf // Elektronikbokstäver. - 1980. - T. 16 , nr. 22 . - S. 860 . - doi : 10.1049/el:19800611 .
• Diogo Vieira Andrade, Luiz Henrique de Figueiredo. Bra approximationer för den relativa grannskapsgrafen // Proc. 13:e kanadensiska konferensen om beräkningsgeometri . – 2001.