Х-стабло

У фракталној геометрији, Х-стабло је фрактална структура стабла конструисаног од нормалних линијских сегмената, где је сваки претходни за квадратни корен од 2 мањи од следећег, већег сегмента. Зове се управо овим именом због тога што његов понављајући шаблон подсећа на латинично слово "Х". Има Хаусдорфову димензију 2, и налази се произвољно близу свакој тачки правоугаоника. Његове апликације укључују ВЛСИ дизајн и инжењеринг микроталаса.

Првих десет нивоа Х-стабла

Конструкција

Х-стабло се може конструисати тако што се полази од линијског сегмента произвољне дужине, цртајући два краћа сегмента под правим углом у односу на почетни сегмент кроз његове крајње тачке, и настављајући у истом маниру, смањујући дужине линијских сегмената у сваком следећем кораку за √2.

Алтернативни процес који генерише исти фрактални сет врши се тако што се почне са правоугаоником чије су странице у размери 1:√2, који је познат и као "сребрни правоугаоник", и који се даље дели на два мања сребрна правоугаоника, док се у сваком следећем кораку линијским сегментом повезују два тежишта два мања правоугаоника. Сличан процес се може извести и са правоугаоницима било које размере страница, међутим само сребрни правоугаоник води равномерном смањењу линијског сегмента у сваком кораку за вредност √2 док се код осталих правоугаоника дужина смањује за различите случајне вредности.

Особине

Х-стабло је себи сличан фрактал; његова Хаусдорфова димензија једнака је 2.

Тачке Х-стабла налазе се произвољно близу свакој тачки правоугаоника (исто као у случају почетног правоугаоника у конструкцији са тежиштима мањих подељених правоугаоника). Међутим, нису укључене све тачке правоугаоника; на пример центар почетног линијског сегмента није укључен.

Апликације

У ВЛСИ дизајну, Х-стабло може да се користи као план за уредјено бинарно стабло користећи целу област која је пропорционална броју чворова стабла. Додатно, Х-стабло формира просторно ефикасан план за стабла у графичком цртању, и велики је део конструкције склопа тачака који служи за решавање проблема трговачког путника.

Често се користи као синхрона мрежа за слање сигнала часовника до свих делова чипа са једнаким кашњењем до сваког дела, а такође се користило и као интерконекциона мрежа за ВЛСИ мултипроцесоре. Из истог разлога, Х-стабло се користи у низу микрострип антена да би се пренео радио сигнал до сваке микрострип антене појединачно са једнаким кашњењем.

Матично Х-стабло може бити генерисано у тродимензионалну структуру додајући линијске сегменте у правцу преноса у плану Х-стабла. Резултирајуће тродимензионално Х-стабло има Хаусдорфову димензију једнаку 3. Откривено је да матично Х-стабло и његова тродимензиона верзија конструишу вештачке електромагнетне атоме у фотоничким кристалима и метаматеријалима и да потенцијално могу имати примену у инжењерингу микроталаса.

Сродни склопови

Х-стабло је пример фракталне мреже у којој је угао између два суседна линијска сегмента увек 180 степени. Због свог својства да се нађе произвољно близу свакој тачки свог граничног правоугаоника такође подсећа на бесконачно густу криву, иако само по себи није крива.

Тополошки, Х-стабло има особине сличне дендриту. Међутим, оно није дендрит: дендрити морају бити затворени склопови, а Х-стабло није затворено (његово затварање представља читав правоугаоник).

Манделброт-стабло је веома блиско повезан фрактал који користи правоугаонике уместо линијских сегмената, у циљу стварања природнијег изгледа. Као компензацију за већу ширину својих компоненти и да би се избегло преклапање, фактор вредности за коју се смањује величина компоненти на сваком нивоу мора бити мало већа од √2.

Литература

• Берн, Марсхалл; Еппстеин, Давид (1993), „Wорст-цасе боундс фор субаддитиве геометриц грапхс”, Проц. 9тх Аннуал Сyмпосиум он Цомпутатионал Геометрy (ПДФ), Ассоциатион фор Цомпутинг Мацхинерy, стр. 183—188, дои:10.1145/160985.161018 .
• Броwнинг, Саллy А. (1980), Тхе Трее Мацхине: А Хигхлy Цонцуррент Цомпутинг Енвиронмент, Пх.D. тхесис, Цалифорниа Институте оф Тецхнологy, Архивирано из оригинала 16. 07. 2012. г., Приступљено 31. 05. 2015 .
• Буркис, Ј. (1991), „Цлоцк трее сyнтхесис фор хигх перформанце АСИЦс”, ИЕЕЕ Интернатионал Цонференце он АСИЦ, стр. 9.8.1—9.8.4, дои:10.1109/АСИЦ.1991.242921 .
• Хоу, Бо; Xие, Ханг; Wен, Wеијиа; Схенг, Пинг (2008), „Тхрее-дименсионал металлиц фрацталс анд тхеир пхотониц црyстал цхарацтеристицс”, Пхyсицал Ревиеw Б, 77: 125113, дои:10.1103/ПхyсРевБ.77.125113 .
• Калосхин, Вадим; Сапрyкина, Мариа (2012), „Ан еxампле оф а неарлy интеграбле Хамилтониан сyстем wитх а трајецторy денсе ин а сет оф маxимал Хаусдорфф дименсион”, Цоммуницатионс ин Матхематицал Пхyсицс, 315 (3): 643—697, МР 2981810, дои:10.1007/с00220-012-1532-x .
• Леисерсон, Цхарлес Е. (1980), „Ареа-еффициент грапх лаyоутс”, 21ст Аннуал Сyмпосиум он Фоундатионс оф Цомпутер Сциенце (ФОЦС 1980), стр. 270—281, дои:10.1109/СФЦС.1980.13 .
• Нгуyен, Qуанг Винх; Хуанг, Мао Лин (2002), „А спаце-оптимизед трее висуализатион”, ИЕЕЕ Сyмпосиум он Информатион Висуализатион, стр. 85—92, дои:10.1109/ИНФВИС.2002.1173152 .
• Уллман, Јеффреy D. (1984), Цомпутатионал Аспецтс оф ВСЛИ, Цомпутер Сциенце Пресс .
• Wен, Wеијиа; Зхоу, Леи; Ли, Јенсен; Ге, Wеикун; Цхан, C. Т.; Схенг, Пинг (2002), Субwавеленгтх пхотониц банд гапс фром планар фрацталс, 89, Пхyсицал Ревиеw Леттерс, стр. 223901, дои:10.1103/ПхyсРевЛетт.89.223901 .

Види још

• Кабаи, С. (2002), Матхематицал Грапхицс I: Лессонс ин Цомпутер Грапхицс Усинг Матхематица, Пüспöкладáнy, Хунгарy: Уницонстант, стр. 231 .
• Лауwериер, Х. (1991), Фрацталс: Ендлесслy Репеатед Геометриц Фигурес, Принцетон, Њ: Принцетон Университy Пресс, стр. 1—2 .

Спољашње везе

• Фамоус Фрацталс - Х-фрацтал
• Wеисстеин, Ериц W. „Х-Фрацтал”. МатхWорлд. 
• Мовинг Х-фрацтал (инцлудинг Јава Апплет)