Beta skelet - Beta skeleton

Kvadrat ichida 100 tasodifiy nuqtadan iborat doiraga asoslangan 1,1-skelet (og'ir quyuq qirralar) va 0,9-skelet (och chiziqli ko'k qirralar).

Yilda hisoblash geometriyasi va geometrik grafik nazariyasi, a β- skelet yoki beta skelet bu yo'naltirilmagan grafik nuqtalar to'plamidan aniqlangan Evklid samolyoti. Ikki nuqta p va q har qanday burchak har doim chekka bilan bog'langan prq raqamli parametrdan aniqlangan chegaradan keskinroqβ.

Doira asosidagi ta'rif

Bo'sh hududlar Rpq doiraga asoslangan holda belgilash β- skelet. Chapda: β <1. Markaz: β = 1. To'g'ri: β > 1.

Ruxsat bering β ijobiy bo'ling haqiqiy raqam va burchakni hisoblang θ formulalar yordamida

Istalgan ikkita nuqta uchun p va q samolyotda, ruxsat bering Rpq qaysi burchak uchun nuqtalar to'plami bo'ling prq dan kattaθ. Keyin Rpq diametri bo'lgan ikkita ochiq diskning birlashishi shaklini oladi .d(p,q) uchun β ≥ 1 va θ ≤ π / 2, va u diametri ikkita ochiq diskning kesishishi shaklini oladi d(p,q)/β uchun β ≤ 1 va θ Π / 2. Qachon β = 1 ikkita formulalar bir xil qiymatni beradi θ = π / 2, va Rpq bilan bitta ochiq disk shaklini oladi pq uning diametri sifatida.

The β- skeletlari topildi diskret to'plam S tekislikdagi nuqtalar yo'naltirilmagan grafik bu ikkita nuqtani birlashtiradi p va q chekka bilan pq har doim Rpq nuqtalari mavjud emas S. Ya'ni β-skeleton - bu mintaqalar tomonidan belgilangan bo'sh mintaqaviy grafik Rpq.[1] Qachon S bir fikrni o'z ichiga oladi r qaysi burchak uchun prq dan katta θ, keyin pq ning chekkasi emas β- skelet; The βskelet shu juftliklardan iborat pq buning uchun bunday nuqta yo'q r mavjud.

Lune-ga asoslangan ta'rif

Ba'zi mualliflar muqobil ta'rifdan foydalanadilar, unda bo'sh hududlar mavjud Rpq uchun β > 1 ikkita diskning birlashmasi emas, aksincha linzalar (ko'pincha shu mazmunda chaqiriladi "Lunes "), ikkita mos keladigan diskning kesishgan diametri .d(pq), shunday qilib, bu segment segmenti pq ikkala diskning radiusida yotadi va shunaqa p va q ikkalasi ham kesishish chegarasida yotadi. Davraga asoslangan kabi βskelet, lune asosidagi βskeletning chekkasi bor pq har doim mintaqa Rpq boshqa kirish punktlaridan bo'sh. Ushbu muqobil ta'rif uchun nisbiy mahalla grafigi a ning alohida ishi β- bilan skelet β = 2. Ikkala ta'rif uchun mos keladi β ≤ 1 va katta qiymatlari uchun β aylana asosidagi skelet a subgraf Lune asosidagi skelet.

Doira asosidagi va lune asosidagi muhim farq β-skeletlari shundaki, bitta chiziqda yotmaydigan har qanday nuqta to'plami uchun har doim etarlicha katta qiymat mavjud β shunday qilib aylanaga asoslangan β- skelet bo'sh grafik. Aksincha, agar bir juft ochko bo'lsa p va q boshqa barcha narsalar uchun xususiyatga ega r, ikkita burchakdan biri pqr va qpr yassi, keyin lune-ga asoslangan βskeletka chekkadan iborat bo'ladi pq qanchalik katta bo'lmasin β bu.

Tarix

β-skeletlari birinchi tomonidan aniqlangan Kirkpatrick va Radke (1985) kabi o'zgarmas ning o'zgarishi alfa shakllari ning Edelsbrunner, Kirkpatrik va Zaydel (1983). Ism "β-skeleton ", ba'zi bir ma'noda β-skelet nuqta to'plami shaklini a kabi tasvirlaydi topologik skelet ikki o'lchovli mintaqaning shaklini tavsiflaydi. Ning bir nechta umumlashtirilishi β- boshqa bo'sh mintaqalar tomonidan belgilangan grafikalar uchun skelet ham ko'rib chiqilgan.[1][2]

Xususiyatlari

Agar β doimiy ravishda 0 dan ∞ gacha o'zgarib turadi, aylana asosidagi β-skeletlari -dan kengaygan grafikalar ketma-ketligini hosil qiladi to'liq grafik uchun bo'sh grafik. Maxsus ish β = 1 ga olib keladi Gabriel grafigi o'z ichiga olganligi ma'lum Evklidning minimal uzunlikdagi daraxti; shuning uchun β-skeletda, shuningdek, Gabriel grafigi va har doim minimal uzunlikdagi daraxt mavjud β ≤ 1.

Har qanday doimiy uchun β, a fraktal ning tekislangan versiyasiga o'xshash qurilish Koch qor yordamida nuqtalar to'plamlari ketma-ketligini aniqlash uchun foydalanish mumkin β-skeletlar - bu birlik kvadrat ichida o'zboshimchalik bilan katta uzunlikdagi yo'llar. Shuning uchun, chambarchas bog'liq bo'lganidan farqli o'laroq Delaunay uchburchagi, βskeletlari chegarasiz streç faktor va yo'q geometrik kalitlar.[3]

Algoritmlar

A sodda algoritm bu har uchtani sinovdan o'tkazadi p, qva r a'zolik uchun r mintaqada Rpq qurish mumkin β- har qanday to'plamning skeletlari topildi n O vaqtidagi ballar (n3).

Qachon β ≥ 1, the β-skelet (ikkala ta'rifi bilan) - bu Gabriel grafigining subgrafasi, ya'ni Delaunay uchburchagi. Agar pq - Delaunay uchburchagining chekkasi emas, bu uning chegarasi emas β- skelet, keyin nuqta r katta burchak hosil qiladi prq bilan uchburchak hosil qiladigan eng ko'p ikkita nuqtadan biri sifatida topish mumkin p va q Delaunay uchburchagida. Shuning uchun, ning bu qiymatlari uchun β, doiraga asoslangan βto'plami uchun skelet n nuqtalarni O (vaqt ichida) qurish mumkinn jurnaln) Delaunay triangulyatsiyasini hisoblash va uning qirralarini filtrlash uchun ushbu test yordamida.[2]

Uchun β <1, ning boshqa algoritmi Xurtado, Liotta va Meijer (2003) qurilishiga imkon beradi β- skelet O (vaqt ichida)n2). Eng yaxshi yomon vaqt chegarasi bo'lishi mumkin emas, chunki har qanday belgilangan qiymat uchun β biridan kichikroq, umumiy holatdagi nuqta to'plamlari mavjud (a ning kichik buzilishlari muntazam ko'pburchak ) buning uchun β-skelet a zich grafik kvadrat qirralarning soni bilan. Xuddi shu kvadratik vaqt ichida, butun β-spektrum (doiraga asoslangan ketma-ketlik β- o'zgaruvchan holda hosil bo'lgan skeletlari topildi β) ham hisoblanishi mumkin.

Ilovalar

To'garakka asoslangan βskelet ishlatilishi mumkin tasvirni tahlil qilish ob'ekt chegarasida namunaviy nuqtalar to'plami berilgan (ikki o'lchovli ob'ekt shaklini qayta tiklash uchun nuqtalarni ulang nuqta bog'lanishi kerak bo'lgan jumboq, jumboqning bir qismi sifatida emas, balki algoritm bilan chiqarilishi kerak). Umuman olganda, bu parametr qiymatini tanlashni talab qiladi β, tanlov ekanligini isbotlash mumkin β = 1.7 har qanday silliq yuzaning butun chegarasini to'g'ri tiklaydi va chegaralarga tegishli bo'lmagan qirralarni hosil qilmaydi, agar namunalar mahalliyga nisbatan etarlicha zich hosil qilingan bo'lsa egrilik yuzaning[4] Ammo eksperimental sinovlarda past qiymat, β = 1.2, a-dagi ko'chalarning markaziy chiziqlarini belgilaydigan nuqtalar to'plamidan ko'cha xaritalarini tiklash uchun yanada samarali bo'ldi geografik axborot tizimi.[5] Umumlashtirish uchun β- yuzalarni uch o'lchovli qayta qurish skeletlari texnikasi, qarang Xiyosi (2007).

Davraga asoslangan β-skeletlari subgrafiyalarini topish uchun ishlatilgan minimal vazn triangulyatsiyasi nuqta to'plamining: ning etarlicha katta qiymatlari uchun β, har bir β- skelet qirrasi minimal vazn uchburchagiga tegishli bo'lishi kafolatlanishi mumkin. Agar shu tarzda topilgan qirralar a hosil qilsa ulangan grafik barcha kirish nuqtalarida, keyin qolgan minimal og'irlikdagi triangulyatsiya qirralarini topish mumkin polinom vaqti tomonidan dinamik dasturlash. Ammo, umuman olganda, minimal og'irlikdagi triangulyatsiya muammosi NP-qattiqdir va shu tarzda topilgan qirralarning pastki qismi ulanmasligi mumkin.[6]

βskeletlari topildi mashinada o'rganish geometrik echish tasnif muammolar[7] va simsiz maxsus tarmoqlar bir-biri bilan aloqa o'rnatishi mumkin bo'lgan simsiz stantsiyalar juftligini tanlash orqali aloqa murakkabligini boshqarish mexanizmi sifatida.[8]

Izohlar

  1. ^ a b Kardinal, Kollette va Langerman (2009).
  2. ^ a b Veltkamp (1992).
  3. ^ Eppshteyn (2002); Bose va boshq. (2002); Vang va boshq. (2003).
  4. ^ Amenta, Bern va Eppshteyn (1998); O'Rourke (2000).
  5. ^ Radke va Flodmark (1999).
  6. ^ Keil (1994); Cheng va Xu (2001).
  7. ^ Chjan va King (2002); Tussaint (2005).
  8. ^ Bxardvaj, Misra va Syu (2005).

Adabiyotlar

  • Amenta, Nina; Bern, Marshal; Eppshteyn, Devid (1998), "Yer po'stlog'i va beta-skelet: kombinatsion egri chiziqni qayta qurish", Grafik modellar va tasvirni qayta ishlash, 60/2 (2): 125-135, arxivlangan asl nusxasi 2006-03-22.
  • Bxardvaj, Manvendu; Misra, Satyajayant; Xue, Guoliang (2005), "ß-skelet yordamida simsiz maxsus tarmoqlarda tarqatilgan topologiyani boshqarish", Yuqori samaradorlikni almashtirish va marshrutlash bo'yicha seminar (HPSR 2005), Gonkong, Xitoy (PDF), dan arxivlangan asl nusxasi (PDF) 2011-06-07 da.
  • Bose, Prosenjit; Devroye, Lyuk; Evans, Uilyam; Kirkpatrik, Devid G. (2002), "Jabroilning grafikalari va βskeletlari topildi ", LATIN 2002: Nazariy informatika, Kompyuter fanidan ma'ruza matnlari, 2286, Springer-Verlag, 77-97 betlar, doi:10.1007/3-540-45995-2_42.
  • Kardinal, Jan; Kollett, Sebastian; Langerman, Stefan (2009), "Bo'sh hudud grafikalari", Hisoblash geometriyasi nazariyasi va qo'llanilishi, 42 (3): 183–195, doi:10.1016 / j.comgeo.2008.09.003.
  • Cheng, Siu-Ving; Xu, Yin-Fen (2001), "Yoqish β- skelet minimal vazn uchburchagi subgrafasi sifatida ", Nazariy kompyuter fanlari, 262 (1–2): 459–471, doi:10.1016 / S0304-3975 (00) 00318-2.
  • Edelsbrunner, Gerbert; Kirkpatrik, Devid G.; Zaydel, Raymund (1983), "Tekislikdagi nuqtalar to'plami shakli to'g'risida", Axborot nazariyasi bo'yicha IEEE operatsiyalari, 29 (4): 551–559, doi:10.1109 / TIT.1983.1056714.
  • Eppshteyn, Devid (2002), "Beta-skeletlari chegarasiz kengaygan", Hisoblash geometriyasi nazariyasi va qo'llanilishi, 23 (1): 43–52, arXiv:cs.CG/9907031, doi:10.1016 / S0925-7721 (01) 00055-4.
  • Xiyoshi, H. (2007), "Uch o'lchamdagi ochko'z beta-skelet", Proc. Fan va muhandislik sohasidagi Voronoi diagrammalariga bag'ishlangan 4-xalqaro simpozium (ISVD 2007), 101-109 betlar, doi:10.1109 / ISVD.2007.27.
  • Xurtado, Ferran; Liotta, Juzeppe; Meijer, Henk (2003), "Yaqinlik grafikalari uchun optimal va suboptimal mustahkam algoritmlar", Hisoblash geometriyasi nazariyasi va qo'llanilishi, 25 (1–2): 35–49, doi:10.1016 / S0925-7721 (02) 00129-3.
  • Keil, J. Mark (1994), "Minimal vazn uchburchagi subgrafasini hisoblash", Hisoblash geometriyasi nazariyasi va qo'llanilishi, 4 (1): 18–26, doi:10.1016/0925-7721(94)90014-0.
  • Kirkpatrik, Devid G.; Radke, Jon D. (1985), "Hisoblash morfologiyasining asoslari", Hisoblash geometriyasi, Mashina razvedkasi va naqshni aniqlash, 2, Amsterdam: Shimoliy-Gollandiya, 217–248 betlar.
  • O'Rourke, Jozef (2000), "Hisoblash geometriyasi 38-ustun", SIGACT yangiliklari, 31 (1): 28–30, arXiv:cs.CG/0001025, doi:10.1145/346048.346050.
  • Radke, Jon D.; Flodmark, Anders (1999), "Ko'chalar markazini qurish uchun fazoviy dekompozitsiyalardan foydalanish" (PDF), Geografik axborot fanlari, 5 (1): 15–23.
  • Tussaint, Godfrid (2005), "Masalaning asosida o'rganish va ma'lumotlarni qazib olishda eng yaqin qo'shni usullarini takomillashtirish uchun geometrik yaqinlik grafikalari", Xalqaro hisoblash geometriyasi va ilovalari jurnali, 15 (2): 101–150, doi:10.1142 / S0218195905001622.
  • Veltkamp, ​​Remko C. (1992), "Γ-mahalla grafigi" (PDF), Hisoblash geometriyasi nazariyasi va qo'llanilishi, 1 (4): 227–246, doi:10.1016 / 0925-7721 (92) 90003-B.
  • Vang, Veyzjao; Li, Sian-Yang; Moaveninejad, Kousha; Vang, Yu; Song, Ven-Chjan (2003), "ning koeffitsienti βskeletlari topildi ", Proc. Hisoblash geometriyasi bo'yicha 15-konferentsiya (CCCG 2003) (PDF), 35-38 betlar.
  • Chjan, Van; King, Irwin (2002), "orqali qo'llab-quvvatlash vektorlarini topish β- skelet texnikasi ", Proc. Asabiy ma'lumotlarni qayta ishlash bo'yicha 9-xalqaro konferentsiya materiallari (ICONIP'02), Orchid Country Club, Singapur, 2002 yil 18-22 noyabr. (PDF), 1423–1427 betlar.