WikiDer > Nisbiy mahalla grafigi

Relative neighborhood graph
Birlik kvadratidagi 100 tasodifiy nuqtaning nisbiy mahalla grafigi.

Yilda hisoblash geometriyasi, nisbiy mahalla grafigi (RNG)) an yo'naltirilmagan grafik nuqtalar to'plamida aniqlangan Evklid samolyoti ikki nuqtani birlashtirib p va q Uchinchi nuqta mavjud bo'lmaganda chekka r bu ikkalasiga ham yaqinroq p va q ular bir-biriga nisbatan. Ushbu grafik tomonidan taklif qilingan Godfrid Tussaint 1980 yilda inshootlar to'plam shakli haqidagi tasavvurlariga mos keladigan nuqtalarni to'plamidan tuzilishni aniqlash usuli sifatida.[1][2]

Algoritmlar

Supowit (1983) O (nisbiy mahalla grafigini qanday qilib samarali tarzda qurish kerakligini ko'rsatdi (n jurnaln) vaqt.[3] Uni O (n) kutilgan vaqt, tasodifiy ballar to'plami uchun bir xil taqsimlangan ichida birlik kvadrat.[4] Nisbatan mahalla grafigini hisoblash mumkin chiziqli vaqt dan Delaunay uchburchagi nuqta to'plami.[5][6]

Umumlashtirish

U faqat nuqtalar orasidagi masofalar bo'yicha aniqlanganligi sababli, har qanday nuqtadagi to'plamlar uchun nisbiy mahalla grafigini aniqlash mumkin o'lchov,[1][7][8] va evklid bo'lmagan o'lchovlar uchun.[1][5][9][10]

Tegishli grafikalar

Nisbatan mahalla grafigi a ga misol ob'ektivasoslangan beta skelet. Bu subgraf ning Delaunay uchburchagi. O'z navbatida, Evklidning minimal uzunlikdagi daraxti uning subgrafidir, shundan kelib chiqadiki a ulangan grafik.

The Urquhart grafigi, Delaunay uchburchagi har uchburchagidan eng uzun qirrasini olib tashlash natijasida hosil bo'lgan grafik dastlab nisbiy mahalla grafigini hisoblashning tezkor usuli sifatida taklif qilingan.[11] Urquhart grafasi ba'zida nisbiy mahalla grafigidan farq qilsa ham[12] undan nisbiy mahalla grafigiga yaqinlashish sifatida foydalanish mumkin.[13]

Adabiyotlar

  1. ^ a b v Tussaint, G. T. (1980), "Sonli planar to'plamning nisbiy mahalla grafigi", Naqshni aniqlash, 12 (4): 261–268, doi:10.1016/0031-3203(80)90066-7.
  2. ^ Yaromchik, JW .; Tussaint, G.T. (1992), "Qarindosh mahalla grafikalari va ularning qarindoshlari", IEEE ish yuritish, 80 (9): 1502–1517, doi:10.1109/5.163414.
  3. ^ Supowit, K. J. (1983), "Minimal uzunlikdagi daraxtlarga ilova qilingan nisbiy mahalla grafigi", J. ACM, 30 (3): 428–448, doi:10.1145/2402.322386.
  4. ^ Katajaynen, Jirki; Nevalainen, Olli; Teuhola, Jukka (1987), "Planar nisbiy qo'shni grafiklarni hisoblash uchun chiziqli kutilgan vaqt algoritmi", Axborotni qayta ishlash xatlari, 25 (2): 77–86, doi:10.1016/0020-0190(87)90225-0.
  5. ^ a b Yaromchik, J. V.; Kovaluk, M. (1987), "Nisbiy mahalla grafikalari to'g'risida eslatma", Proc. 3-simp. Hisoblash geometriyasi, Nyu-York, Nyu-York, AQSh: ACM, 233–241 betlar, doi:10.1145/41958.41983.
  6. ^ Lingas, A. (1994), "Delaunay uchburchagidan nisbiy mahalla grafigini chiziqli vaqt ichida qurish", Hisoblash geometriyasi, 4 (4): 199–208, doi:10.1016/0925-7721(94)90018-3.
  7. ^ Yaromchik, J. V.; Kovaluk, M. (1991), "3 o'lchovli evklid fazosida nisbiy mahalla grafigini qurish", Alohida dastur. Matematika., 31 (2): 181–191, doi:10.1016 / 0166-218X (91) 90069-9.
  8. ^ Agarval, Pankaj K.; Mataušek, Jiři (1992), "Uch o'lchovdagi nisbiy mahalla grafikalari", Proc. 3-ACM-SIAM simptomi. Alohida algoritmlar, 58-65-betlar.
  9. ^ O'Rourke, J. (1982), "ichidagi nisbiy mahalla grafigini hisoblash L1 va L∞ metrikalar ", Naqshni aniqlash, 15 (3): 189–192, doi:10.1016 / 0031-3203 (82) 90070-X.
  10. ^ Li, D. T. (1985), "nisbiy mahalla grafikalari L1-metrik ", Naqshni aniqlash, 18 (5): 327–332, doi:10.1016/0031-3203(85)90023-8.
  11. ^ Urquhart, R. B. (1980), "Nisbiy mahalla grafigini hisoblash algoritmlari", Elektron xatlar, 16 (14): 556–557, doi:10.1049 / el: 19800386.
  12. ^ Tussaint, G. T. (1980), "Izoh: nisbiy mahalla grafigini hisoblash algoritmlari", Elektron xatlar, 16 (22): 860, doi:10.1049 / el: 19800611. Urquhart tomonidan javob, 860-861 betlar.
  13. ^ Andrade, Diogo Vieyra; de Figueiredo, Luiz Henrique (2001), "Nisbiy mahalla grafigi uchun yaxshi taxminlar", Proc. Hisoblash geometriyasi bo'yicha 13-Kanada konferentsiyasi (PDF).