Δέντρο H

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

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

Κατασκευή

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

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

Ιδιότητες

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

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

Εφαρμογές

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

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

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

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

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

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

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

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

Δείτε επίσης

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

Παραπομπές

• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.

Πρότυπο:Authority control Πρότυπο:Portal bar