Δέντρο H

Τα δέκα πρώτα επίπεδα ενός δέντρου H

Στην μορφοκλασματική γεωμετρία, το δέντρο H είναι μια φράκταλ δενδροειδή δομή που κατασκευάζεται από κάθετα ευθύγραμμα τμήματα, καθένα από τα οποία είναι μικρότερο κατά έναν παράγοντα της τετραγωνικής ρίζας του 2 από το επόμενο μεγαλύτερο γειτονικό τμήμα. Ονομάζεται έτσι επειδή το επαναλαμβανόμενο μοτίβο του μοιάζει με το γράμμα "Η". Έχει διάσταση Χάουστορφ 2 και πλησιάζει αυθαίρετα σε κάθε σημείο ενός ορθογωνίου. Οι εφαρμογές του περιλαμβάνουν τη σχεδίαση VLSI και τη μηχανική μικροκυμάτων.

Κατασκευή

Το δέντρο H μπορεί να σχεδιαστεί ξεκινώντας με ένα ευθύγραμμο τμήμα αυθαίρετου μήκους, σχεδιάζοντας δύο μικρότερα τμήματα σε ορθή γωνία με το πρώτο μέσω των τελικών του σημείων και συνεχίζοντας με τον ίδιο τρόπο, μειώνοντας (διαιρώντας) το μήκος των ευθύγραμμων τμημάτων που σχεδιάζονται σε κάθε στάδιο κατά ${\sqrt {2}}$. Θα μπορούσε επίσης να οριστεί μια παραλλαγή αυτής της κατασκευής στην οποία το μήκος σε κάθε επανάληψη πολλαπλασιάζεται με λόγο μικρότερο από $1/{\sqrt {2}}$, αλλά για αυτή την παραλλαγή το σχήμα που προκύπτει καλύπτει μόνο ένα μέρος του ορθογωνίου που το οριοθετεί, με ένα φράκταλ όριο .

Μια εναλλακτική διαδικασία που παράγει το ίδιο μορφοκλασματικό σύνολο είναι να ξεκινήσουμε με ένα ορθογώνιο με πλευρές στον λόγο $1:{\sqrt {2}}$, και να το διχοτομήσουμε επανειλημμένα σε δύο μικρότερα ασημένια ορθογώνια, συνδέοντας σε κάθε στάδιο τα δύο κεντροειδή των δύο μικρότερων ορθογωνίων με ένα ευθύγραμμο τμήμα. Μια παρόμοια διαδικασία μπορεί να πραγματοποιηθεί με ορθογώνια οποιουδήποτε άλλου σχήματος, αλλά το ορθογώνιο $1:{\sqrt {2}}$ οδηγεί στο μέγεθος του ευθύγραμμου τμήματος να μειώνεται ομοιόμορφα κατά έναν παράγοντα ${\sqrt {2}}$ σε κάθε βήμα, ενώ για άλλα ορθογώνια το μήκος θα μειώνεται κατά διαφορετικούς παράγοντες σε περιττά και ζυγά επίπεδα της αναδρομικής κατασκευής.

Ιδιότητες

Το δέντρο H είναι ένα αυτο-ομοιόμορφο φράκταλ- η διάσταση Χάουστορφ είναι ίση με 2.

Τα σημεία του δέντρου H έρχονται αυθαίρετα κοντά σε κάθε σημείο σε ένα ορθογώνιο (το ίδιο με το αρχικό ορθογώνιο στην κατασκευή από κεντροειδή υποδιαιρεμένων ορθογωνίων). Εντούτοις, δεν περιλαμβάνει όλα τα σημεία του ορθογωνίου- παραδείγματος χάριν, τα σημεία στην κάθετη διχοτόμο του αρχικού ευθύγραμμου τμήματος (εκτός από το μέσο του τμήματος αυτού) δεν περιλαμβάνονται.

Εφαρμογές

Τρισδιάστατο δέντρο H

Στη σχεδίαση VLSI, το δέντρο H μπορεί να χρησιμοποιηθεί ως διάταξη για ένα πλήρες δυαδικό δέντρο με συνολική επιφάνεια ανάλογη του αριθμού των κόμβων του δέντρου. Επιπλέον, το δέντρο H αποτελεί μια χωροταξική διάταξη για δέντρα στη σχεδίαση γραφημάτων και ως μέρος μιας κατασκευής ενός συνόλου σημείων για τα οποία το άθροισμα των τετραγωνικών μηκών ακμών της περιήγησης του ταξιδιώτη πωλητή είναι μεγάλο. Χρησιμοποιείται συνήθως ως δίκτυο διανομής ρολογιού για τη δρομολόγηση σημάτων χρονισμού σε όλα τα μέρη ενός chip με ίσες καθυστερήσεις διάδοσης σε κάθε μέρος, και έχει επίσης χρησιμοποιηθεί ως δίκτυο διασύνδεσης για πολυεπεξεργαστές VLSI. .

Το επίπεδο δέντρο H μπορεί να γενικευτεί στην τρισδιάστατη δομή μέσω της προσθήκης τμημάτων γραμμών στην κατεύθυνση κάθετα στο επίπεδο του δέντρου H. Το τρισδιάστατο δέντρο H που προκύπτει έχει διάσταση Χάουστορφ ίση με 3. Το επίπεδο δέντρο H και η τρισδιάστατη εκδοχή του έχει βρεθεί ότι αποτελούν τεχνητά ηλεκτρομαγνητικά άτομα σε φωτονικούς κρυστάλλους και μεταϋλικά και μπορεί να έχουν πιθανές εφαρμογές στη μηχανική μικροκυμάτων.

Σχετικά σύνολα

Αυτο-επικαλυπτόμενο φράκταλ θόλος με οξύτερες γωνίες από το δέντρο H

Το δέντρο H είναι ένα παράδειγμα μορφοκλασματικού θόλου, στο οποίο η γωνία μεταξύ γειτονικών τμημάτων γραμμής είναι πάντα 180 μοίρες. Ως προς την ιδιότητά του να πλησιάζει αυθαίρετα σε κάθε σημείο του ορθογωνίου που το οριοθετεί, μοιάζει επίσης με μια καμπύλη πλήρωσης του χώρου, αν και το ίδιο δεν είναι καμπύλη.

Από τοπολογικής άποψης, ένα δέντρο H έχει ιδιότητες παρόμοιες με εκείνες ενός δενδροειδούς. Ωστόσο, δεν είναι δενδροειδή: τα δενδροειδή πρέπει να είναι κλειστά σύνολα, και τα δέντρα H δεν είναι κλειστά (το κλείσιμό τους είναι ολόκληρο το ορθογώνιο).

Παραλλαγές της ίδιας δενδρικής δομής με παχύτερα πολυγωνικά κλαδιά στη θέση των ευθύγραμμων τμημάτων του δέντρου H έχουν οριστεί από τον Μπενουά Μάντελμπροτ και μερικές φορές ονομάζονται δέντρο Μάντελμπροτ. Σε αυτές τις παραλλαγές, για να αποφευχθούν επικαλύψεις μεταξύ των φύλλων του δέντρου και των παχύτερων κλάδων τους, ο συντελεστής κλίμακας κατά τον οποίο μειώνεται το μέγεθος σε κάθε επίπεδο πρέπει να είναι ελαφρώς μεγαλύτερος από ${\sqrt {2}}$.

Δείτε επίσης

• Αναδρομή
• Σύνολο Μάντελμπροτ
• Σύνολο Julia
• Οικοδομήσιμο Σύμπαν

Παραπομπές

• Bern, Marshall; Eppstein, David (1993), «Worst-case bounds for subadditive geometric graphs», Proc. 9th Annual Symposium on Computational Geometry, Association for Computing Machinery, σελ. 183–188, doi:10.1145/160985.161018, http://www.ics.uci.edu/~eppstein/pubs/BerEpp-SCG-93.pdf .
• Browning, Sally A. (1980), The Tree Machine: A Highly Concurrent Computing Environment, Ph.D. thesis, California Institute of Technology, http://authors.library.caltech.edu/26932/, ανακτήθηκε στις 2023-09-11 .
• Burkis, J. (1991), «Clock tree synthesis for high performance ASICs», IEEE International Conference on ASIC, σελ. 9.8.1–9.8.4, doi:10.1109/ASIC.1991.242921 .
• Hou, Bo; Xie, Hang; Wen, Weijia; Sheng, Ping (2008), «Three-dimensional metallic fractals and their photonic crystal characteristics», Physical Review B 77 (12): 125113, doi:10.1103/PhysRevB.77.125113, http://repository.ust.hk/ir/bitstream/1783.1-25969/1/PhysRevB.77.125113.pdf .
• Kaloshin, Vadim; Saprykina, Maria (2012), «An example of a nearly integrable Hamiltonian system with a trajectory dense in a set of maximal Hausdorff dimension», Communications in Mathematical Physics 315 (3): 643–697, doi:10.1007/s00220-012-1532-x .
• Lauwerier, Hans (1991), Fractals: Endlessly Repeated Geometrical Figures, Princeton Science Library, 6, Princeton University Press, ISBN 9780691024455 
• Leiserson, Charles E. (1980), «Area-efficient graph layouts», 21st Annual Symposium on Foundations of Computer Science (FOCS 1980), σελ. 270–281, doi:10.1109/SFCS.1980.13 .
• Nguyen, Quang Vinh; Huang, Mao Lin (2002), «A space-optimized tree visualization», IEEE Symposium on Information Visualization, σελ. 85–92, doi:10.1109/INFVIS.2002.1173152 .
• Ullman, Jeffrey D. (1984), Computational Aspects of VSLI, Computer Science Press .
• Wen, Weijia; Zhou, Lei; Li, Jensen; Ge, Weikun; Chan, C. T.; Sheng, Ping (2002), «Subwavelength photonic band gaps from planar fractals», Physical Review Letters 89 (22): 223901, doi:10.1103/PhysRevLett.89.223901, PMID 12485068, http://repository.ust.hk/ir/bitstream/1783.1-49380/1/PhysRevLett.89.223901.pdf .