Κανόνας πεπερασμένης υποδιαίρεσης

Στα μαθηματικά, ένας κανόνας πεπερασμένης υποδιαίρεσης είναι ένας αναδρομικός τρόπος διαίρεσης ενός πολυγώνου ή άλλου δισδιάστατου σχήματος σε όλο και μικρότερα τεμάχια. Οι κανόνες υποδιαίρεσης είναι κατά μία έννοια γενικεύσεις των κανονικών γεωμετρικών φράκταλ. Αντί να επαναλαμβάνουν το ίδιο ακριβώς σχέδιο ξανά και ξανά, έχουν μικρές παραλλαγές σε κάθε στάδιο, επιτρέποντας μια πλουσιότερη δομή, διατηρώντας παράλληλα το κομψό ύφος των φράκταλ. Οι κανόνες υποδιαίρεσης έχουν χρησιμοποιηθεί στην αρχιτεκτονική, τη βιολογία και την επιστήμη των υπολογιστών, καθώς και στη μελέτη των υπερβολικών πολλαπλών. Τα πλακίδια αντικατάστασης είναι ένας καλά μελετημένος τύπος κανόνα υποδιαίρεσης.

Ορισμός

Ένας κανόνας υποδιαίρεσης χρησιμοποιεί ένα πλακίδιο του επιπέδου με πολύγωνα και το μετατρέπει σε ένα νέο πλακίδιο υποδιαιρώντας κάθε πολύγωνο σε μικρότερα πολύγωνα. Είναι πεπερασμένος αν υπάρχουν μόνο πεπερασμένοι τρόποι με τους οποίους κάθε πολύγωνο μπορεί να υποδιαιρεθεί. Κάθε τρόπος υποδιαίρεσης ενός πλακιδίου ονομάζεται τύπος πλακιδίου. Κάθε τύπος πλακιδίου αντιπροσωπεύεται από μια ετικέτα (συνήθως ένα γράμμα). Κάθε τύπος πλακιδίου υποδιαιρείται σε μικρότερους τύπους πλακιδίων. Κάθε ακμή υποδιαιρείται επίσης σύμφωνα με πεπερασμένα πολλά είδη ακμών. Οι πεπερασμένοι κανόνες υποδιαίρεσης μπορούν να υποδιαιρέσουν μόνο πλακίδια που αποτελούνται από πολύγωνα με ετικέτες από τύπους πλακιδίων. Τέτοια πλακίδια ονομάζονται σύμπλοκα υποδιαίρεσης για τον κανόνα υποδιαίρεσης. Δεδομένου οποιουδήποτε συμπλέγματος υποδιαίρεσης για έναν κανόνα υποδιαίρεσης, μπορούμε να το υποδιαιρέσουμε ξανά και ξανά για να πάρουμε μια ακολουθία από πλακίδια .

Παραδείγματος χάριν, η δυαδική υποδιαίρεση έχει έναν τύπο πλακιδίων και έναν τύπο ακμών:


Δεδομένου ότι ο μόνος τύπος πλακιδίων είναι το τετράπλευρο, η δυαδική υποδιαίρεση μπορεί να υποδιαιρέσει μόνο πλακίδια που αποτελούνται από τετράπλευρα. Αυτό σημαίνει ότι τα μόνα σύμπλοκα υποδιαίρεσης είναι πλακοστρώσεις από τετράπλευρα. Το πλακίδιο μπορεί να είναι κανονικό, χωρίς όμως να είναι απαραίτητο:


Εδώ ξεκινάμε με ένα σύμπλεγμα από τέσσερα τετράπλευρα και το υποδιαιρούμε δύο φορές. Όλα τα τετράπλευρα είναι πλακίδια τύπου Α.

Παραδείγματα κανόνων πεπερασμένης υποδιαίρεσης

Η βαρυκεντρική υποδιαίρεση είναι ένα παράδειγμα κανόνα υποδιαίρεσης με έναν τύπο ακμής (που υποδιαιρείται σε δύο ακμές) και έναν τύπο πλακιδίου (ένα τρίγωνο που υποδιαιρείται σε 6 μικρότερα τρίγωνα). Οποιαδήποτε τριγωνική επιφάνεια είναι ένα σύμπλεγμα βαρυκεντρικής υποδιαίρεσηςJ. W. Cannon, W. J. Floyd, W. R. Parry. Finite subdivision rules. Conformal Geometry and Dynamics, vol. 5 (2001), pp. 153–196..

Το πλακίδιο Πενρόζε μπορεί να παραχθεί από έναν κανόνα υποδιαίρεσης σε ένα σύνολο τεσσάρων τύπων πλακιδίων (οι καμπύλες γραμμές στον παρακάτω πίνακα βοηθούν μόνο να δείξουν πώς τα πλακίδια ταιριάζουν μεταξύ τους):

 Όνομα Αρχικά πλακίδια Γενιά 1 Γενιά 2 Γενιά 3 Μισός χαρταετός 120px 120px 120px 120px Μισό βέλος 120px 120px 120px 120px Ήλιος 120px 120px 120px 120px Αστέρι 120px 120px 120px 120px

Ορισμένοι ορθολογικοί χάρτες οδηγούν σε κανόνες πεπερασμένης υποδιαίρεσηςJ. W. Cannon, W. J. Floyd, W. R. Parry. Constructing subdivision rules from rational maps. Conformal Geometry and Dynamics, vol. 11 (2007), pp. 128–136.  Αυτό περιλαμβάνει τους περισσότερους χάρτες LattèsJ. W. Cannon, W. J. Floyd, W. R. Parry. Lattès maps and subdivision rules. Conformal Geometry and Dynamics, vol. 14 (2010, pp. 113–140..

Κάθε πρώτος, μη διαιρεμένος εναλλασσόμενος κόμβος ή συμπλήρωμα συνδέσμου έχει έναν κανόνα υποδιαίρεσης, με κάποια πλακίδια που δεν υποδιαιρούνται, που αντιστοιχούν στο όριο του συμπληρώματος συνδέσμου.B. Rushton. Constructing subdivision rules from alternating links. Conform. Geom. Dyn. 14 (2010), 1–13. Οι κανόνες υποδιαίρεσης δείχνουν πώς θα έμοιαζε ο νυχτερινός ουρανός σε κάποιον που ζει σε ένα συμπλήρωμα κόμβου- επειδή το σύμπαν τυλίγεται γύρω από τον εαυτό του (δηλαδή δεν είναι απλά συνδεδεμένο), ένας παρατηρητής θα έβλεπε το ορατό σύμπαν να επαναλαμβάνεται σε ένα άπειρο μοτίβο. Ο κανόνας υποδιαίρεσης περιγράφει αυτό το μοτίβο.

Ο κανόνας υποδιαίρεσης φαίνεται διαφορετικός για διαφορετικές γεωμετρίες. Αυτός είναι ένας κανόνας υποδιαίρεσης για τον τρίφυλλο κόμβο, ο οποίος δεν είναι υπερβολικός κόμβος:


Και αυτός είναι ο κανόνας υποδιαίρεσης για τους δακτυλίους Borromean, ο οποίος είναι υπερβολικός:


Σε κάθε περίπτωση, ο κανόνας υποδιαίρεσης ενεργεί σε κάποιο πλακίδιο της σφαίρας (π.χ. στον νυχτερινό ουρανό), αλλά είναι ευκολότερο να σχεδιάσουμε απλώς ένα μικρό μέρος του νυχτερινού ουρανού, που αντιστοιχεί σε ένα μόνο πλακίδιο που υποδιαιρείται επανειλημμένα. Αυτό συμβαίνει για τον κόμβο του τριφυλλιού:

300px|none|Υποδιαιρέσεις του συμπλέγματος υποδιαιρέσεων για το συμπλήρωμα τριφυλλιού.

Και για τα δαχτυλίδια Borromean:

300px|none|Υποδιαιρέσεις του συμπλέγματος υποδιαιρέσεων για το συμπλήρωμα των δακτυλίων Borromean.

Κανόνες υποδιαίρεσης σε υψηλότερες διαστάσεις
Οι κανόνες υποδιαίρεσης μπορούν εύκολα να γενικευτούν σε άλλες διαστάσεις. Επίσης, η δυαδική υποδιαίρεση μπορεί να γενικευτεί σε άλλες διαστάσεις (όπου οι υπερκύβοι διαιρούνται από κάθε μεσαίο επίπεδο), όπως στην απόδειξη του θεωρήματος Χάινε- Μπορέλ.

Αυστηρός ορισμός
Ένας κανόνας πεπερασμένης υποδιαίρεσης   αποτελείται από τα εξής.

1. Ένα πεπερασμένο 2-διάστατο σύμπλεγμα CW , το οποίο αποκαλείται σύμπλεγμα υποδιαίρεσης, με σταθερή δομή κελιών, έτσι ώστε το  να είναι η ένωση των κλειστών 2 κελιών του. Υποθέτουμε ότι για κάθε κλειστό 2-κύτταρο  του  υπάρχει μια δομή CW  σε ένα κλειστό 2-δίσκο έτσι ώστε το  να έχει τουλάχιστον δύο κορυφές, οι κορυφές και οι ακμές του  να περιέχονται στο , και ο χαρακτηριστικός χάρτης  που απεικονίζει πάνω στο  περιορίζεται σε ομοιομορφισμό πάνω σε κάθε ανοικτό κελί.

2. Ένα πεπερασμένο δισδιάστατο σύμπλεγμα CW , το οποίο αποτελεί υποδιαίρεση του .

3.Ένας συνεχής κυψελοειδής χάρτης  που ονομάζεται χάρτης υποδιαίρεσης, του οποίου ο περιορισμός σε κάθε ανοιχτό κελί είναι ομοιομορφισμός σε ένα ανοιχτό κελί.

Κάθε σύμπλεγμα CW  στον παραπάνω ορισμό (με τον δεδομένο χαρακτηριστικό του χάρτη ) ονομάζεται τύπος πλακιδίου.

Ένα σύμπλεγμα  για έναν κανόνα υποδιαίρεσης  είναι ένα 2-διάστατο σύμπλεγμα CW  που είναι η ένωση των κλειστών 2 κελιών του, μαζί με έναν συνεχή κυτταρικό χάρτη  του οποίου ο περιορισμός σε κάθε ανοικτό κελί είναι ομοιομορφισμός. Μπορούμε να υποδιαιρέσουμε το  σε ένα σύμπλεγμα  απαιτώντας ότι ο επαγόμενος χάρτης  περιορίζεται σε ομοιομορφισμό σε κάθε ανοικτό κελί. Το  είναι πάλι ένα -σύμπλεγμα με χάρτη . Επαναλαμβάνοντας αυτή τη διαδικασία, λαμβάνουμε μια ακολουθία υποδιαιρεμένων -συμπλεγμάτων  με χάρτες .

Η δυαδική υποδιαίρεση είναι ένα παράδειγμα:


Το σύμπλεγμα υποδιαίρεσης μπορεί να δημιουργηθεί με τη συγκόλληση των απέναντι άκρων του τετραγώνου, μετατρέποντας το σύμπλεγμα υποδιαίρεσης  σε τόρο. Ο χάρτης υποδιαίρεσης  είναι ο χάρτης διπλασιασμού στον τόρο, τυλίγοντας τον μεσημβρινό γύρω από τον εαυτό του δύο φορές και το γεωγραφικό μήκος γύρω από τον εαυτό του δύο φορές. Πρόκειται για έναν χάρτη τετραπλής κάλυψης. Το επίπεδο, πλακοστρωμένο με τετράγωνα, είναι ένα σύμπλεγμα υποδιαίρεσης για αυτόν τον κανόνα υποδιαίρεσης, με τον χάρτη δομής  που δίνεται από τον τυπικό χάρτη κάλυψης. Με την υποδιαίρεση, κάθε τετράγωνο στο επίπεδο υποδιαιρείται σε τετράγωνα του ενός τετάρτου του μεγέθους.

Ιδιότητες οιονεί ισομετρίας

Οι κανόνες υποδιαίρεσης μπορούν να χρησιμοποιηθούν για τη μελέτη των οιονεί ισομετρικών ιδιοτήτων ορισμένων χώρων. Με δεδομένο έναν κανόνα υποδιαίρεσης  και ένα σύμπλεγμα υποδιαίρεσης , µπορούµε να κατασκευάσουµε ένα γράφηµα που ονοµάζεται ιστορικό γράφηµα και καταγράφει τη δράση του κανόνα υποδιαίρεσης. Αυτός ο γράφος αποτελείται από τους διπλούς γράφους κάθε βήματος , και τις άκρες που συνδέουν κάθε πλακίδιο στο  με τις υποδιαιρέσεις του στο .

Οι ιδιότητες οιονεί ισομετρίας του γραφήματος ιστορίας μπορούν να μελετηθούν με τη χρήση κανόνων υποδιαίρεσης. Παραδείγματος χάριν, ο γράφος ιστορίας είναι οιονεί ισομετρικός με τον υπερβολικό χώρο ακριβώς όταν ο κανόνας υποδιαίρεσης είναι σύμμορφος, όπως περιγράφεται στο συνδυαστικό θεώρημα απεικόνισης του Ρίμαν.

Εφαρμογές

Τα κεραμίδια Girih της ισλαμικής αρχιτεκτονικής είναι αυτοομοειδή κεραμίδια που μπορούν να διαμορφωθούν με πεπερασμένους κανόνες υποδιαίρεσης. Το 2007, ο Πίτερ Τζ. Λου του Πανεπιστημίου Χάρβαρντ και ο καθηγητής Πολ Τζ. Στάινχαρντ του Πανεπιστημίου Πρίνστον δημοσίευσαν μια εργασία στο περιοδικό Science, στην οποία προτείνουν ότι τα κεραμίδια Girih διαθέτουν ιδιότητες συμβατές με τα αυτο-ομοειδή οιονεί κρυσταλλικά μορφοκλασματικά κεραμίδια, όπως τα κεραμίδια Penrose (παρουσίαση 1974, προγενέστερες εργασίες που ξεκίνησαν γύρω στο 1964), τα οποία προηγούνται κατά πέντε αιώνες .

Οι επιφάνειες υποδιαίρεσης στα γραφικά υπολογιστών χρησιμοποιούν κανόνες υποδιαίρεσης για να βελτιώσουν μια επιφάνεια σε ένα δεδομένο επίπεδο ακρίβειας. Αυτές οι επιφάνειες υποδιαίρεσης (όπως η επιφάνεια υποδιαίρεσης Catmull-Clark) παίρνουν ένα πλέγμα πολυγώνων (ο τύπος που χρησιμοποιείται στις τρισδιάστατες ταινίες κινουμένων σχεδίων) και το βελτιώνουν σε ένα πλέγμα με περισσότερα πολύγωνα προσθέτοντας και μετακινώντας σημεία σύμφωνα με διάφορους αναδρομικούς τύπουςD. Zorin. Subdivisions on arbitrary meshes: algorithms and theory. Institute of Mathematical Sciences (Singapore) Lecture Notes Series. 2006.. Αν και πολλά σημεία μετακινούνται κατά τη διαδικασία αυτή, κάθε νέο πλέγμα είναι, από συνδυαστική άποψη, μια υποδιαίρεση του παλιού πλέγματος (πράγμα που σημαίνει ότι για κάθε ακμή και κορυφή στο παλιό πλέγμα, μπορείτε να προσδιορίσετε μια αντίστοιχη ακμή και κορυφή στο νέο πλέγμα, καθώς και αρκετές άλλες άκρες και κορυφές).

Οι κανόνες υποδιαίρεσης εφαρμόστηκαν από τους Cannon, Floyd και Parry (2000) στη μελέτη των μοτίβων ανάπτυξης μεγάλης κλίμακας των βιολογικών οργανισμώνJ. W. Cannon, W. Floyd and W. Parry. Crystal growth, biological cell growth and geometry. Pattern Formation in Biology, Vision and Dynamics, pp. 65–82. World Scientific, 2000. , .. Οι Cannon, Floyd και Parry ανέπτυξαν ένα μαθηματικό πρότυπο ανάπτυξης το οποίο έδειξε ότι ορισμένα συστήματα που καθορίζονται από απλούς πεπερασμένους κανόνες υποδιαίρεσης μπορούν να οδηγήσουν σε αντικείμενα (στο παράδειγμά τους, έναν κορμό δέντρου) των οποίων η μορφή μεγάλης κλίμακας ταλαντώνεται άγρια με την πάροδο του χρόνου, παρόλο που οι τοπικοί νόμοι υποδιαίρεσης παραμένουν οι ίδιοι. Οι Cannon, Floyd και Parry εφάρμοσαν επίσης το μοντέλο τους στην ανάλυση των προτύπων ανάπτυξης των ιστών αρουραίων. Πρότειναν ότι η "αρνητικά καμπυλωτή" (ή μη ευκλείδεια) φύση των μικροσκοπικών προτύπων ανάπτυξης των βιολογικών οργανισμών είναι ένας από τους βασικούς λόγους για τους οποίους οι οργανισμοί μεγάλης κλίμακας δεν μοιάζουν με κρυστάλλους ή πολυεδρικά σχήματα αλλά στην πραγματικότητα σε πολλές περιπτώσεις μοιάζουν με αυτοομοιόμορφα φράκταλ. Ειδικότερα, πρότειναν ότι μια τέτοια "αρνητικά καμπυλωτή" τοπική δομή εκδηλώνεται στην ιδιαίτερα διπλωμένη και ιδιαίτερα συνδεδεμένη φύση του εγκεφάλου και του πνευμονικού ιστού.

Η εικασία Cannon
Οι Cannon, Floyd και Parry μελέτησαν για πρώτη φορά τους κανόνες πεπερασμένης υποδιαίρεσης σε μια προσπάθεια να αποδείξουν την ακόλουθη εικασία:

Η εικασία Cannon: Κάθε υπερβολική ομάδα Γκρόμοφ με μια 2-σφαίρα στο άπειρο δρα γεωμετρικά στον υπερβολικό 3-χώροJames W. Cannon. The combinatorial Riemann mapping theorem. Acta Mathematica 173 (1994), no. 2, pp. 155–234..

Εδώ, μια γεωμετρική δράση είναι μια συμπαγής, κατάλληλα ασυνεχής δράση με ισομετρίες. Αυτή η εικασία λύθηκε εν μέρει από τον Γκριγκόρι Πέρελμαν (Grigory Perelman) στην απόδειξη της εικασίας της γεωμετρίας, η οποία δηλώνει (εν μέρει) ότι κάθε υπερβολική ομάδα Γκρόμοφ που είναι ομάδα 3-πολλαπλοτήτων πρέπει να δρα γεωμετρικά στον υπερβολικό 3-χώρο. Ωστόσο, απομένει ακόμη να αποδειχθεί ότι μια υπερβολική ομάδα Γκρόμοφ με 2 σφαίρες στο άπειρο είναι μια ομάδα 3-πολλαπλοτήτων.

Οι Cannon και Σουένσον έδειξανJ. W. Cannon and E. L. Swenson, Recognizing constant curvature discrete groups in dimension 3. Transactions of the American Mathematical Society 350 (1998), no. 2, pp. 809–849. ότι μια υπερβολική ομάδα με μια 2-σφαίρα στο άπειρο έχει έναν σχετικό κανόνα υποδιαίρεσης. Αν αυτός ο κανόνας υποδιαίρεσης είναι σύμμορφος με μια ορισμένη έννοια, η ομάδα θα είναι μια ομάδα 3-πολλαπλών με τη γεωμετρία του υπερβολικού 3-χώρου .

Συνδυαστικό θεώρημα απεικόνισης Ρίμαν
Οι κανόνες υποδιαίρεσης δίνουν μια ακολουθία από πλακίδια μιας επιφάνειας, και τα πλακίδια δίνουν μια ιδέα της απόστασης, του μήκους και του εμβαδού (αφήνοντας κάθε πλακίδιο να έχει μήκος και εμβαδόν 1). Στο όριο, οι αποστάσεις που προκύπτουν από αυτά τα πλακίδια μπορεί να συγκλίνουν κατά κάποιο τρόπο σε μια αναλυτική δομή στην επιφάνεια. Το Συνδυαστικό Θεώρημα Χαρτογράφησης Ρίμαν δίνει αναγκαίες και ικανές συνθήκες για να συμβεί αυτό.

Η διατύπωσή της χρειάζεται κάποιο υπόβαθρο. Ένα πλακίδιο  ενός δακτυλίου   (δηλαδή, ένας κλειστός δακτύλιος) δίνει δύο αναλλοίωτες,  και , που ονομάζονται προσεγγιστικά moduli. Αυτά είναι παρόμοια με τα κλασικά modulus ενός δακτυλίου. Ορίζονται με τη χρήση συναρτήσεων βάρους. Μια συνάρτηση βάρους  αναθέτει έναν μη αρνητικό αριθμό που ονομάζεται βάρος σε κάθε πλακίδιο του . Σε κάθε μονοπάτι στο   μπορεί να δοθεί ένα μήκος, που ορίζεται ως το άθροισμα των βαρών όλων των πλακιδίων στο μονοπάτι. Ορίζουμε το ύψος  του  υπό  ως το infimum του μήκους όλων των πιθανών μονοπατιών που συνδέουν το εσωτερικό όριο του  με το εξωτερικό όριο. Η περίμετρος  του  υπό  είναι το infimum του μήκους όλων των δυνατών μονοπατιών που κυκλώνουν τον δακτύλιο (δηλαδή δεν είναι μηδενικά ομοιογενή στο R). Το εμβαδόν  του  υπό  ορίζεται ως το άθροισμα των τετραγώνων όλων των βαρών στο  . Στη συνέχεια, ορίζουμε ότι





Να σημειωθεί ότι είναι αναλλοίωτες σε αλλαγές στην κλίμακα της μετρικής.

Μια ακολουθία  από πλακίδια είναι σύμμορφη () αν το πλέγμα πλησιάζει το 0 και:

 Για κάθε δακτύλιο , τα προσεγγιστικά moduli  και , για όλα τα  επαρκώς μεγάλα, βρίσκονται σε ένα ενιαίο διάστημα της μορφής και
 Δίνεται ένα σημείο  i στην επιφάνεια, μια γειτονιά  του  και ένας ακέραιος , υπάρχει ένας δακτύλιος  στο  που διαχωρίζει το x από το συμπλήρωμα του , έτσι ώστε για όλα τα μεγάλα  τα προσεγγιστικά moduli του  να είναι όλα μεγαλύτερα από το . 

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

Συνέπειες
Το Θεώρημα Συνδυαστικής Απεικόνισης Ρίμαν υποδηλώνει ότι μια ομάδα  δρα γεωμετρικά στην  αν και μόνο αν είναι υπερβολική κατά Gromov, έχει μια σφαίρα στο άπειρο και ο φυσικός κανόνας υποδιαίρεσης στη σφαίρα οδηγεί σε μια ακολουθία πλακοστρώσεων που είναι σύμμορφη με την παραπάνω έννοια. Έτσι, η εικασία Cannon θα ήταν αληθής αν όλοι αυτοί οι κανόνες υποδιαίρεσης ήταν σύμμορφοι.

 Εξωτερικός σύνδεσμος  
 Bill Floyd's research page. This page contains most of the research papers by Cannon, Floyd and Parry on subdivision rules, as well as a gallery of subdivision rules.

 Δείτε επίσης 
Αλγόριθμος διαμαντιού τετραγώνου
Καμπύλη που γεμίζει το χώρο
Νιφάδα του Κοχ 
Καμπύλη Χίλμπερτ
Καμπύλη του δράκου
Σπόγγος του Μένγκερ

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

Παραπομπές



Κατηγορία:Φράκταλ
Κατηγορία:Γεωμετρία