Joyni to'ldiradigan daraxt - Space-filling tree

Joyni to'ldiradigan daraxtlar o'xshash bo'lgan geometrik konstruktsiyalardir bo'shliqni to'ldiradigan egri chiziqlar,^[1] lekin dallanadigan, daraxtga o'xshash tuzilishga ega va ildiz otgan. Bo'shliqni to'ldiruvchi daraxt o'sib boruvchi jarayon bilan belgilanadi, natijada daraxtning har bir nuqtasi unga yaqinlashadigan cheklangan uzunlikdagi yo'lga ega bo'ladi. Aksincha bo'shliqni to'ldiradigan egri chiziqlar, daraxtdagi individual yo'llar qisqa bo'lib, bo'shliqning istalgan qismiga ildizdan tezda etib borishga imkon beradi.^[2]^[3] Joyni to'ldiradigan daraxtlarning eng oddiy misollari odatiy, o'ziga o'xshash, fraktal tuzilishi, lekin odatiy bo'lmagan va hatto tenglashtirilishi mumkin tasodifiy /Monte-Karlo variantlar (qarang Tasodifiy daraxtni tezda o'rganish ). Joyni to'ldiradigan daraxtlar tabiatdagi qiziqarli o'xshashliklarga ega, shu jumladan suyuqlik tarqatish tizimlari, qon tomir tarmoqlari va fraktal o'simliklarning o'sishi va ko'plab qiziqarli aloqalar L tizimlari kompyuter fanida.

Ta'rif

Bo'shliqni to'ldiruvchi daraxt takrorlanadigan jarayon bilan belgilanadi, bunda a ning bitta nuqtasi davomiy fazo uzluksiz yo'l orqali kosmosdagi har bir boshqa nuqtaga cheklangan uzunlik va kosmosdagi har bir nuqta uchun kamida bitta yo'l bor yaqinlashadi unga.

Ushbu ma'noda "bo'shliqni to'ldiruvchi daraxt" atamasi 2009 yilgi texnik hisobotda yaratilgan ^[4] "bo'shliqni to'ldirish" va "daraxt" ni matematikada an'anaviy ta'riflaridan farqli ravishda belgilaydi. Tushuntirilganidek bo'shliqni to'ldiradigan egri chiziq maqola, 1890 yilda Peano bo'shliqni to'ldiradigan birinchi egri chiziqni topdi va Iordaniya 1887 ta'rifi, hozirgi kunda standart bo'lib, egri chiziq funktsiyalar ketma-ketligi emas, balki bitta funktsiya. Egri chiziq "bo'shliqni to'ldirish" dir, chunki u "diapazoni butun 2 o'lchovli birlik kvadratini o'z ichiga olgan egri chiziq" (birinchi jumlasida tushuntirilganidek) bo'shliqni to'ldiradigan egri chiziq ).

Aksincha, texnik hisobotda belgilangan bo'shliqni to'ldiradigan daraxt bitta daraxt emas. Bu faqat daraxtlarning ketma-ketligi. Gazetada "bo'shliqni to'ldiruvchi daraxt aslida daraxtlarning cheksiz ketma-ketligi sifatida ta'riflanadi" deb yozilgan. Bu belgilaydi ${ displaystyle T _ { text {square}}}$ "daraxtlar ketma-ketligi" sifatida, keyin " ${ displaystyle T _ { text {square}}}$ "bu bo'shliqni to'ldiruvchi daraxt". Bu odatiy ma'noda bo'shliqni to'ldiruvchi emas, balki butun 2 o'lchovli birlik kvadratini o'z ichiga oladi. Buning o'rniga, qog'oz uni ketma-ketlikdagi daraxtlar o'zboshimchalik bilan har bir nuqtaga yaqinlashishini aniqlaydi. Daraxtlar ketma-ketligi T bo'shliqda "bo'shliqni to'ldirish" deb nomlanadi X agar har biri uchun bo'lsa x ∈ X, daraxtda ildizdan boshlanib, unga yaqinlashadigan yo'l mavjudxUshbu kontseptsiyaning standart atamasi shundaki, u bir qator fikrlarni o'z ichiga oladi hamma joyda zich birlik maydonida.

Misollar

Bo'sh joyni to'ldiradigan daraxtning eng oddiy misoli - a ni to'ldiradi kvadrat planar mintaqa. Tasvirlar planar mintaqa uchun qurilishni tasvirlaydi ${ displaystyle [0,1] ^ {2} subset mathbb {R} ^ {2}}$ . Har bir takrorlashda mavjud daraxtlarga qo'shimcha novdalar qo'shiladi.

Kvadrat maydonni to'ldiradigan daraxt (takrorlash 1)
Kvadrat maydonni to'ldiradigan daraxt (takrorlash 2)
Kvadrat maydonni to'ldiradigan daraxt (takrorlash 3)
Kvadrat maydonni to'ldiradigan daraxt (takrorlash 4)
Kvadrat maydonni to'ldiradigan daraxt (takrorlash 5)
Kvadrat maydonni to'ldiradigan daraxt (takrorlash 6)

Bo'shliqni to'ldiruvchi daraxtlarni turli xil shakllar va hajmlar uchun ham belgilash mumkin: quyida uchburchak shaklidagi maydonni to'ldirishni aniqlash uchun bo'linish sxemasi keltirilgan bo'lib, har bir takrorlanishda mavjud daraxtlarga qo'shimcha shoxchalar qo'shilib, har biri uchburchak to'rtta pastki uchburchakning markazlariga.

Uchburchak bo'shliqni to'ldiradigan daraxtning dastlabki uchta takrorlanishiga bo'linish sxemasi

Uchburchak bo'shliqni to'ldiradigan daraxtning dastlabki oltita takrorlanishi quyida keltirilgan:

Uchburchak bo'shliqni to'ldiradigan daraxt (takrorlash 1)
Uchburchak bo'shliqni to'ldiradigan daraxt (takrorlash 2)
Uchburchak bo'shliqni to'ldiradigan daraxt (takrorlash 3)
Uchburchak bo'shliqni to'ldiradigan daraxt (takrorlash 4)
Uchburchak bo'shliqni to'ldiradigan daraxt (takrorlash 5)
Uchburchak bo'shliqni to'ldiradigan daraxt (takrorlash 6)

Joyni to'ldiradigan daraxtlarni yuqori o'lchamlarda ham qurish mumkin. Eng oddiy misollar kublar yilda ${ displaystyle mathbb {R} ^ {3}}$ va giperkubiklar yilda ${ displaystyle mathbb {R} ^ {n}}$ . Uchun ishlatiladigan takrorlanishlarning o'xshash ketma-ketligi kvadrat bo'shliqni to'ldiradigan daraxt giperkubkalar uchun ishlatilishi mumkin. Bunday bo'shliqni to'ldiradigan daraxtning uchinchi takrorlanishi ${ displaystyle mathbb {R} ^ {3}}$ quyida tasvirlangan:

Bo'sh joyni to'ldiradigan kub (takrorlash 3)

Shuningdek qarang

Adabiyotlar

^ Sagan, H. va J. Xolbruk: "Bo'shliqni to'ldiruvchi egri chiziqlar", Springer-Verlag, Nyu-York, 1994 y
^ Kuffner, J. J. va S. M. LaValle: Joyni to'ldiradigan daraxtlar, Robototexnika instituti, Karnegi Mellon universiteti, CMU-RI-TR-09-47, 2009 y.
^ Kuffner, J. J .; LaValle, SM; "Joyni to'ldiruvchi daraxtlar: harakatni rejalashtirishni izchil izlashning yangi istiqbollari", Intelligent Robots and Systems (IROS), 2011 IEEE / RSJ Xalqaro konferentsiyasi, jild, №, s. 2199-2206, 25-30 sentyabr. 2011 yil
^ Kuffner, J. J. va S. M. LaValle: Joyni to'ldiradigan daraxtlar, Robototexnika instituti, Karnegi Mellon universiteti, CMU-RI-TR-09-47, 2009 y.

[1] Sagan, H. va J. Xolbruk: "Bo'shliqni to'ldiruvchi egri chiziqlar", Springer-Verlag, Nyu-York, 1994 y

[2] Kuffner, J. J. va S. M. LaValle: Joyni to'ldiradigan daraxtlar, Robototexnika instituti, Karnegi Mellon universiteti, CMU-RI-TR-09-47, 2009 y.

[3] Kuffner, J. J .; LaValle, SM; "Joyni to'ldiruvchi daraxtlar: harakatni rejalashtirishni izchil izlashning yangi istiqbollari", Intelligent Robots and Systems (IROS), 2011 IEEE / RSJ Xalqaro konferentsiyasi, jild, №, s. 2199-2206, 25-30 sentyabr. 2011 yil

[4] Kuffner, J. J. va S. M. LaValle: Joyni to'ldiradigan daraxtlar, Robototexnika instituti, Karnegi Mellon universiteti, CMU-RI-TR-09-47, 2009 y.

[1]

[2]

[3]

[4]