Relativ nabolagsgraf

En relativ naboskabsgraf er en urettet graf defineret på et sæt punkter i det euklidiske plan ved at forbinde to punkter p og q med en kant, når der ikke er noget tredje punkt r , der er tættere på både p og q end p og q er til hver Andet. Denne graf blev foreslået af Godfried Toussaint i 1980 som en måde at definere en struktur på et sæt punkter, der afspejler den menneskelige opfattelse af sættets form [1] [2] [3] .

Algoritmer

Supovit [4] viste, hvordan man effektivt bygger en relativ nabolagsgraf i O( n  log  n ) tid [5] . Grafen kan beregnes i gennemsnitstid O ( n ) for et vilkårligt sæt af punkter ensartet fordelt i enhedskvadraten [6] . Den relative nabograf kan beregnes i lineær tid ud fra Delaunay-trianguleringen af ​​et sæt punkter [7] [8] .

Generaliseringer

Da en graf kun er defineret med hensyn til afstande mellem punkter, kan en relativ nabograf defineres for sæt af punkter i et rum af enhver dimension [1] [9] og for ikke-euklidiske metrikker [1] [7] [10 ] [11] .

Relaterede grafer

Den relative nabolagsgraf er et eksempel på en beta - kerne . Dette er en undergraf i Delaunay-trianguleringen . Til gengæld er det euklidiske minimumspændingstræ dens undergraf, hvilket antyder, at det er en forbundet graf .

Urquhart-grafen , dannet ved at fjerne den længste kant fra hver trekant i en Delaunay-triangulering, blev oprindeligt foreslået som en hurtig metode til at beregne en relativ nabolagsgraf [12] . Selvom Urquhart-grafen nogle gange er forskellig fra den relative nabolagsgraf [13] , kan den bruges som en tilnærmelse til den relative nabolagsgraf [14] .

Noter

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

Litteratur

• Toussaint GT Den relative nabolagsgraf for et endeligt plant sæt // Mønstergenkendelse. - 1980. - T. 12 , no. 4 . — S. 261–268 . - doi : 10.1016/0031-3203(80)90066-7 .
• Jaromczyk JW, Toussaint GT Relative nabolagsgrafer og deres slægtninge // Proceedings of the IEEE. - 1992. - T. 80 , no. 9 . - S. 1502-1517 . - doi : 10.1109/5.163414 .
• Supowit KJ Den relative nabolagsgraf, med en applikation til minimumspændende træer // J. ACM . - 1983. - T. 30 , no. 3 . — S. 428–448 . - doi : 10.1145/2402.322386 .
• Jyrki Katajainen, Olli Nevalainen, Jukka Teuhola. En lineær forventet-tidsalgoritme til beregning af plane relative nabolagsgrafer // Information Processing Letters. - 1987. - T. 25 , no. 2 . — s. 77–86 . - doi : 10.1016/0020-0190(87)90225-0 .
• Jaromczyk JW, Kowaluk M. En note om relative nabolagsgrafer // Proc. 3. Symp. Beregningsgeometri. - New York, NY, USA: ACM, 1987. - S. 233-241. doi : 10.1145 / 41958.41983 .
• Lingas A. En lineær-tidskonstruktion af den relative nabograf fra Delaunay-trianguleringen // Computational Geometry. - 1994. - T. 4 , no. 4 . — S. 199–208 . - doi : 10.1016/0925-7721(94)90018-3 .
• Jaromczyk JW, Kowaluk M. Konstruktion af den relative nabolagsgraf i 3-dimensionelt euklidisk rum // Diskret Appl. Math.. - 1991. - V. 31 , no. 2 . — S. 181–191 . - doi : 10.1016/0166-218X(91)90069-9 .
• Pankaj K. Agarwal, Jiri Matousek. Relative nabolagsgrafer i tre dimensioner // Proc. 3. ACM–SIAM Symp. Diskrete algoritmer . - 1992. - S. 58-65.
• O'Rourke J. Beregning af den relative nabolagsgraf i L 1 og L ∞ metrics // Mønstergenkendelse. - 1982. - T. 15 , no. 3 . — S. 189–192 . - doi : 10.1016/0031-3203(82)90070-X .
• Lee DT Relative nabolagsgrafer i L 1 -metrikken // Mønstergenkendelse. - 1985. - T. 18 , no. 5 . — S. 327–332 . - doi : 10.1016/0031-3203(85)90023-8 .
• Urquhart RB Algoritmer til beregning af relativ nabolagsgraf // Elektronikbogstaver. - 1980. - T. 16 , no. 14 . — S. 556–557 . - doi : 10.1049/el:19800386 .
• Toussaint GT Kommentar: Algoritmer til beregning af relativ naboskabsgraf // Elektronikbogstaver. - 1980. - T. 16 , no. 22 . - S. 860 . - doi : 10.1049/el:19800611 .
• Diogo Vieira Andrade, Luiz Henrique de Figueiredo. Gode ​​tilnærmelser til den relative nabolagsgraf // Proc. 13. canadisk konference om beregningsgeometri . – 2001.