Yaxshi ajratilgan juftlik parchalanishi - Well-separated pair decomposition - Wikipedia

Yilda hisoblash geometriyasi, a yaxshi ajratilgan parchalanish (WSPD) ochkolar to'plami , bu juft to'plamlar ketma-ketligi , shunday qilib har bir juftlik yaxshi ajratilganva har ikkala alohida nuqta uchun , ikkalasini ajratib turadigan bitta juftlik mavjud.

Yaxshi ajratilgan juftlik parchalanishi natijasida hosil bo'lgan grafik a funktsiyasini bajarishi mumkin k-kalit ning to'liq Evklidlar grafigi, va bunga oid bir nechta muammolarni echimini taxminiy aniqlashda foydalidir.[1]

Ta'rif

Yaxshi ajratilgan juftlikni ingl

Ruxsat bering ikkita ajratilgan nuqta to'plami bo'ling , ni belgilang o'q bilan tekislangan minimal cheklash qutisi ochkolari uchun va ni belgilang ajratish omili.

Biz ko'rib chiqamiz va bolmoq yaxshi ajratilgan, agar har biri uchun bo'lsa va mavjud a d-to'p radiusning uni o'z ichiga olgan holda, ikkita sharning kamida masofa kamida bo'lishi kerak .[2]

Ning pastki qismlarining yaxshi ajratilgan ketma-ketligini ko'rib chiqamiz , bo'lish a yaxshi ajratilgan parchalanish (WSPD) ning har qanday ikkita alohida nuqta uchun bo'lsa , aniq bitta mavjud , , shunday ham

  • va , yoki
  • va .[1]

Qurilish

Bo'lingan daraxt

A qurish yo'li bilan adolatli bo'lingan daraxt, WSPD hajmini qurish mumkin yilda vaqt.[2]

Nuqta to'plamining bo'linish daraxtining umumiy printsipi S bu har bir tugun siz daraxtning nuqtalari to'plamini anglatadi Ssiz va bu cheklov qutisi R (S.siz) ning Ssiz eng uzun tomoni bo'ylab ikkita bolani tashkil etuvchi ikkita teng qismga bo'linadi siz va ularning nuqtalari. To'plamda bitta nuqta bo'lguncha u rekursiv tarzda amalga oshiriladi.

Ruxsat bering Lmaksimal(R (X)) nuqta to'plamining chegaralovchi giper to'rtburchagi eng uzun intervalining hajmini belgilang X va ruxsat bering Lmen(R (X)) hajmini bildiring men- nuqta to'plamining chegaralovchi giper to'rtburchagi o'lchovi X. Split tree hisoblash uchun quyida pseudocode beramiz.

SplitTree (S)    Ruxsat bering siz tugun bo'lishi S    agar | S | = 1        R (u): = R (S) // R (S) har bir tomonning uzunligi nolga teng bo'lgan giper to'rtburchak. Saqlash siz S.dagi yagona nuqta boshqa        Hisoblash R (S)        Ruxsat bering men- uchinchi o'lchov qaerda bo'lishi kerak Lmaksimal(R (S)) = Lmen(R (S))        Split R (S) bo'ylab men- ikkita bir xil o'lchamdagi giper to'rtburchaklardagi uchinchi o'lchov va ikkala to'plamni hosil qilish uchun ushbu giper to'rtburchaklardagi nuqtalarni oling Sv va Sw.        v: = SplitTree (S.v)        w: = SplitTree (S.)w)        Do'kon v va w sifatida, mos ravishda, chap va o'ng farzandlari siz.        R (u): = R (S)    qaytish siz

Ushbu algoritm ishlaydi vaqt.

Biz ishlaydigan yanada samarali algoritmni beramiz vaqt quyida. Maqsad faqat ro'yxatni ko'rib chiqish rekursiyaning bir qadamidagi operatsiyalar, lekin har safar rekursiyani faqat ko'pi bilan yarim nuqtaga chaqiradi.

Ruxsat bering Smenj bo'lishi j-ning koordinatasi men- uchinchi nuqta S shu kabi S har bir o'lchov uchun tartiblangan va p (S.menj) nuqta bo'lishi. Shuningdek, ruxsat bering h (R (S)) ning eng uzun tomonini ajratuvchi giperplane bo'ling R (S) ikkitasida. Psevdo-koddagi algoritm:

SplitTree (S, u)    agar | S | = 1        R (u): = R (S) // R (S) har bir tomonning uzunligi nolga teng bo'lgan giper to'rtburchak. Saqlash siz yagona nuqta S.    boshqa        hajmi: = | S |        takrorlang            Hisoblash R (S)            R (u): = R (S)            j: = 1            k: = | S |            Ruxsat bering men- uchinchi o'lchov qaerda bo'lishi kerak Lmaksimal(R (S)) = Lmen(R (S))            Sv : = ∅            Sw : = ∅            esa Smenj + 1  va Smenk-1 > h (R (S))                hajmi: = hajmi - 1                Sv : = Sv ∪ {p (S_i ^ j)}                Sw : = Sw ∪ {p (S_i ^ k)}                j: = j + 1                k: = k - 1                        Ruxsat bering v va w navbati bilan, chap va o'ng farzandlari siz.            agar Smenj + 1 > h (R (S))                Sw : = S  Sv                u: = w                S: = Sw                SplitTree (Svv)            boshqa bo'lsa Smenk-1                 Sv : = S  Sw                u: = v                S: = Sv                SplitTree (Sww)        qadar hajmi sizen2        SplitTree (S, u)

Har bir tugun uchun saralangan ro'yxatlarni saqlab turish uchun bog'langan ro'yxatlar qo'llaniladi. Har bir ro'yxat uchun boshqalar o'zaro faoliyat ko'rsatgichlar doimiy vaqt ichida bir nuqtani olishlari uchun saqlanadi. Yuqoridagi algoritmda tsiklning har bir takrorlanishida rekursiyaga chaqiruv amalga oshiriladi. Darhaqiqat, ro'yxatni qayta tiklash uchun qo'shimcha punktlarga murojaat qilmasdan, barcha tugunlar ularning tugunlariga tayinlangandan keyin tartiblangan ro'yxatlarni qayta tiklash kerak. Qayta tiklashni amalga oshirish uchun har bir o'lchov bo'yicha har bir ro'yxat bo'ylab yurib, har bir nuqtani uning tugunlarining mos keladigan ro'yxatiga qo'shing va yangi ro'yxatlar uchun o'zaro faoliyat ko'rsatgichlarni qo'shish uchun asl ro'yxatdagi o'zaro faoliyat ko'rsatgichlarni qo'shing. Va nihoyat, har bir tugundagi rekursiyani va uning to'plamini chaqiring.

WSPD hisoblash

Chegaralangan qutilar bilan hisoblangan yaxshi ajratilgan juftlikning vizual ko'rinishi

WSPD-ni rekursivni chaqirish orqali bunday bo'lingan daraxtdan olish mumkin FindPairs (v, w) bolalaridagi funktsiya har bir bo'lingan daraxtdagi tugun. Ruxsat bering sizl / sizr tugunning bolalarini belgilang siz. Biz uchun psevdokod beramiz FindWSPD (T, lar) Quyidagi funktsiya.

FindWSPD (T, lar)    har biriga tugun siz bu bo'lingan daraxtdagi barg emas T qil        FindPairs (ul, ur)

Biz uchun psevdokod beramiz FindPairs (v, w) Quyidagi funktsiya.

FindPairs (v, w)    agar Sv va Sw jihatidan yaxshi ajratilgan s         hisobot juftlik (S.v, Sw)    boshqa        agar( Lmaksimal(R (v)) ≤ Lmaksimal(R (w)) ) Rekursiv ravishda qo'ng'iroq qiling FindPairs (v, wl) va FindPairs (v, wr)        boshqa            Rekursiv qo'ng'iroq FindPairs (vlw) va FindPairs (vrw)

Birlashtirib s-ning barcha qo'ng'iroqlaridan yaxshi ajratilgan juftliklar FindPairs (v, w) ajratish uchun WSPD-ni beradi s.

Algoritmning to'g'riligini isbotlash

Algoritm tomonidan qaytarilgan juftliklar funktsiyaning qaytish sharti tufayli yaxshi ajratilganligi aniq FindPairs.

Endi biz buni har qanday aniq fikr uchun isbotlashimiz kerak va yilda , noyob juftlik mavjud shunday qilib (i) va yoki (ii) va . (I) ega bo'lgan umumiylikni yo'qotmasdan taxmin qiling.

Ruxsat bering ning eng past umumiy ajdodi bo'ling va bo'lingan daraxtda va ruxsat bering va ning farzandlari bo'ling . Oxirgi taxmin tufayli, subtree-da va subtree-da . Qo'ng'iroq FindPairs (v, w) albatta amalga oshiriladi FindWSPD. Har safar rekursiya bo'lganida, rekursiya daraxti joriy rekursion chaqiruvning barcha nuqtalarini o'z ichiga olgan ikkita novdani hosil qiladi, shuning uchun chaqiruvlar ketma-ketligi bo'ladi FindPairs ega bo'lishiga olib keladi yilda va yilda .

Chunki ning eng past umumiy ajdodi va , qo'ng'iroq qilish FindPairs yuqori tugun bolalariga olib keladi va juftlikda bo'lmaslik va qo'ng'iroq qilish FindPairs ning pastki daraxtlaridan birining tugunlaridan biridagi bolalarga natijada bo'ladi yoki hech qanday juftlikda bo'lmaslik. Shunday qilib, juftlik ajratib turadigan noyob narsa va .

Har safar rekursiya daraxti ikkiga bo'linganda, parchalanishga yana bitta juft qo'shiladi. Shunday qilib, algoritmning ishlash muddati oxirgi parchalanishdagi juftlar sonida.

Kallaxan va Kosaraju ushbu algoritm kattaligi bo'yicha yaxshi ajratilgan juftlik parchalanishini (WSPD) topishini isbotladilar .[2]

Xususiyatlari

Lemma 1: Ruxsat bering nisbatan yaxshi ajratilgan juftlik bo'ling . Ruxsat bering va . Keyin, .

Isbot: Chunki va bir xil to'plamda, bizda bor qayerda ning atrofidagi doiraning radiusi va . Chunki va yaxshi ajratilgan ikkita to'plamda, bizda bunga ega . Biz quyidagilarni olamiz:

Lemma 2: Ruxsat bering nisbatan yaxshi ajratilgan juftlik bo'ling . Ruxsat bering va . Keyin, .

Isbot: Uchburchak tengsizligi bo'yicha bizda:

Lemma 1 dan quyidagilarni olamiz:

Ilovalar

Yaxshi ajratilgan juftlik parchalanishi bir qator muammolarni hal qilishda qo'llanishga ega. WSPD quyidagilar uchun ishlatilishi mumkin:

  • Hal qiling eng yaqin juftlik muammosi yilda vaqt.[1]
  • Hal qiling k- eng yaqin juftliklar muammosi vaqt.[1]
  • Hal qiling k- eng yaqin juftlik muammosi vaqt.[3]
  • Hal qiling eng yaqin qo'shnilar muammosi yilda vaqt.[1]
  • Ta'minlash a -taxminiy ning diametri belgilangan nuqta vaqt.[1]
  • To'g'ridan-to'g'ri a t-kalit nuqta to'plami.[1]
  • Ning t ga yaqinlashishini keltiring Evklidning minimal uzunlikdagi daraxti d o'lchovlarda vaqt.[1]
  • Ta'minlash a - ning yaqinlashishi Evklidning minimal uzunlikdagi daraxti d o'lchovlarda vaqt.[4]

Adabiyotlar

  1. ^ a b v d e f g h Smid, Michiel (2005 yil 16-avgust). "Yaxshi ajratilgan juftlik parchalanishi va uning qo'llanilishi" (PDF). Olingan 26 mart 2014.
  2. ^ a b v Callahan, P. B. & Kosaraju, S. R. (1995 yil yanvar). "Ko'p o'lchovli nuqta to'plamlarining parchalanishi, k-eng yaqin qo'shnilar va n-tanadagi potentsial maydonlarga qo'llanilishi bilan". ACM jurnali. 42 (1): 67–90. doi:10.1145/200836.200853.
  3. ^ Bespamyatnix, Sergey; Segal, Maykl (2002). "Masofalarni yaqinlashtirishning tez algoritmlari". Algoritmika. 33 (2): 263–269. doi:10.1007 / s00453-001-0114-7.
  4. ^ Arya, Sunil; Mount, David M. (2016). "Taxminan evklid minimal uzunlikdagi daraxtlarni hisoblashning tezkor va sodda algoritmi". Yigirma ettinchi yillik ACM-SIAM diskret algoritmlari bo'yicha simpoziumi materiallari..