«Ο Αρχιμήδης θα μνημονευθεί όταν ο Αισχύλος θα έχει λησμονηθεί, διότι οι γλώσσες πεθαίνουν, μα οι μαθηματικές ιδέες όχι.» G.Hardy


Κυριακή 20 Αυγούστου 2017

Διαγράμματα Voronoi, η φύλαξη των δασών και ο πανταχού παρών Ευκλείδης



 
  «Σε ηλικία 12 ετών δοκίμασα μια δεύτερη,τελείως διαφορετική έκπληξη:σε ένα μικρό βιβλίο Ευκλείδειας επίπεδης Γεωμετρίας….Εδώ υπήρχαν ισχυρισμοί,όπως για παράδειγμα ότι τα τρία ύψη ενός τριγώνου τέμνονται στο ίδιο σημείο,οι οποίοι αν και καθόλου προφανείς-μπορούν ωστόσο να αποδειχτούν με τέτοια βεβαιότητα,ώστε να μη χωρεί η παραμικρή αμφιβολία.Αυτή η σαφήνεια και βεβαιότητα μου προξένησαν μιαν εντύπωση που δεν μπορεί να περιγραφεί.Το γεγονός ότι,τα αξιώματα έπρεπε να γίνουν δεκτά χωρίς απόδειξη δεν με ενόχλησε.Σε κάθε περίπτωση,μου αρκούσε πλήρως το γεγονός ότι μπορούσα να στηρίζω τις αποδείξεις σε προτάσεις,η εγκυρότητα των οποίων ήταν για μένα αναμφισβήτητη.»
                                                                                                        Άλμπερτ Αϊνστάιν


   Πολύ συχνά βλέπουμε στην Ελλάδα  καταστροφές με τις πυρκαγιές και πέρα από το τραγικό της ιστορίας,θυμήθηκα ένα ωραίο βιβλιαράκι που διάβασα το χειμώνα για την χρήση των μαθηματικών στον πραγματικό κόσμο με τίτλο Figuring out. Entertaining encounters with everyday math και συγγραφέα τον μαθηματικό Nuno Crato,ένα Πορτογάλο πανεπιστημιακό με πραγματικό ταλέντο στην εκλαΐκευση.Σε ένα από τα  κεφάλαια του βιβλίου, ο Crato  πραγματεύεται  τα διαγράμματα Voronoi,την φύλαξη του δάσους από τις πυρκαγιές και πως η ευκλείδεια γεωμετρία ακόμα βρίσκει εφαρμογές στις μέρες μας.Ομολογώ ότι εξεπλάγην ευχάριστα,καθώς βρήκα στο διαδίκτυο εκτενείς αναφορές και αξιολογότατες εργασίες από Έλληνες συναδέλφους.Έτσι λοιπόν,μια ανάρτηση σεντόνι για την πρόληψη των πυρκαγιών και την υπολογιστική γεωμετρία.
Διαγράμματα Voronoi
  Τα πραγματεύτηκε  το 1908,ο μαθηματικός Georgi Voronoi ,όμως,ψήγματα της ιδέας συναντάμε ήδη από το 1644 στο έργο του Καρτέσιου και μεταγενέστερα στον Γερμανό μαθηματικό G.I.Dirichlet (έχουν εναλλακτική ονομασία πλακοστρώσεις Dirichlet),το 1855 τα χρησιμοποίησε ο Jonn Snow (καμία σχέση με το Game of thrones) για τον εντοπισμό εστίας μόλυνσης χολέρας σε ένα πηγάδι στην Broad street  στο Βρετανικό Σόχο,
   Ο Georgi Feodosevich Voronoi γεννήθηκε το 1869 στο Zhuraski,στην Ουκρανία (τότε άνηκε στην Ρωσία).Σπούδασε στο πανεπιστήμιο της Αγίας Πετρούπολης, όπου το 1897,εκπόνησε και το διδακτορικό του. Ακολούθως,στο ίδιο πανεπιστήμιο δίδαξε ως καθηγητής. Πέθανε στην Βαρσοβία το 1908,μόλις 40 ετών.Ο Voronoi ασχολήθηκε με την θεωρία αριθμών και την υπολογιστική  γεωμετρία.Το τελευταίο χρόνο της ζωής του,δημοσίευσε μια μελέτη για την διαμέριση  του  επιπέδου σε τομείς έτσι ώστε να ικανοποιούνται συγκεκριμένα κριτήρια, μια μελέτη  που έμελλε να πάρει το όνομα του, διαγράμματα Voronoi.Πολύ αργότερα,το 1991 τα διαγράμματα του βρήκαν εφαρμογή στην μετεωρολογία και το 1927 στην κρυσταλλογραφία.Αλλά στις μέρες μας τα διαγράμματα Voronoi  χρησιμοποιούνται ευρέως στην υπολογιστική γεωμετρία,ένα κλάδο των μαθηματικών που  χρησιμοποιεί αλγορίθμους  για την επίλυση πραγματικών γεωμετρικών προβλημάτων.Ειδικότερες εφαρμογές του κλάδου: Ιατρική, βιολογία,ρομποτική,τηλεπικοινωνίες (επιλογή εμβέλειας κεραιών στα τηλεφωνικά δίκτυα), προσδιορισμός ΑΟΖ  μιας χώρας.

Για τί ακριβώς μιλάμε;
  Φανταστείτε ένα δάσος που πρέπει να εποπτευθεί για εστίες φωτιάς από δυο ομάδες πυροσβεστών,(S1,S2),καθεμιά τους είναι τοποθετημένη  ένα υπερυψωμένο πύργο (πυροφυλάκιο).Το ερώτημα είναι πως θα χωρίσουμε το δάσος σε τομείς επόπτευσης για να γίνει καλύτερα η παρακολούθηση και ακολούθως η γρήγορη μετάβαση στην φωτιά;Θεωρούμε ότι η θέση των πυροφυλακίων είναι καθορισμένη και δεν μπορούμε να την αλλάξουμε.
Κάνουμε μια  απλή σκέψη. Ενώνουμε με ένα ευθύγραμμο τμήμα τα δυο πυροφυλάκια S1,S2 ,τώρα από το μέσο του ευθύγραμμου τμήματος φέρνουμε μια ευθεία κάθετη στο ευθύγραμμο τμήμα ( μεσοκάθετος),θα χωρίσει το δάσος σε δυο ημιεπίπεδα q2, q1 έτσι ώστε  όλα τα δέντρα στο ένα ημιεπίπεδο  q1 είναι εγγύτερα  στο πυροφυλάκιο  S1 ενώ τα δέντρα στο άλλο ημιεπίπεδο q2 είναι πιο κοντά στο άλλο πυροφυλάκιο S2.



Αν είχαμε 3 πυροφυλάκια  που δεν είναι όλα τοποθετημένα στην ίδια ευθεία το πρόβλημα θα
άλλαζε. Σε αυτήν την περίπτωση έπρεπε να χωρίσουμε το δάσος σε τρεις τομείς  και να αναθέσουμε την εποπτεία καθενός σε ένα πυροφυλάκιο.O διαχωρισμός θα γίνει με ημιευθείες.
Πρέπει να επεκτείνουμε το προηγούμενο διάγραμμα με τα S1,S2  με ένα ακόμα πυροφυλάκιο το S3.
Αρχικά βρίσκουμε το πυροφυλάκιο που είναι πιο κοντά στο S3 ,στο σχήμα είναι το S2  κατόπιν φέρνουμε την μεσοκάθετο του S2S3 χωρίς να επιτρέψουμε να επεκταθεί πέραν της μεσοκαθέτου του S1S2.Το ίδιο κάνουμε και με την μεσοκάθετο του S1S3.Οι ημιευθείες L1,L2,L3  ορίζουν τους τομείς ευθύνης των S1,S2,S3.Οι ημιευθείες  έχουν κοινή αρχή το σημείο τομής των μεσοκαθέτων των πλευρών του τρίγωνου ( περίκεντρο)



Όσο αυξάνεται το πλήθος των πυροφυλακίων τόσο πιο δύσκολο γίνεται να χωρίσουμε το δάσος σε τομείς ευθύνης.Οι τομείς έχουν μορφή  πολυγώνων που θα τους «λείπει» μία πλευρά.(ονομάζονται κελιά). 
Αν έχουμε 4 πυροφυλάκια S1,S2,S3,S4 τότε το χωρίζουμε τετράπλευρο S1S2S4S3, σε δυο τρίγωνα (τριγωνοποίηση)  S1S2S3 ,S2S3S4  κατόπιν βρίσκουμε τα περίκεντρα τους Λ,Κ και  ενώνουμε τα περίκεντρα με τα μέσα των μη κοινών πλευρών του τριγώνων  δηλ τις S1S2, S1S3, S2S4, S3S4, κατόπιν ενώνουμε τα περίκεντρα μεταξύ τους.



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



Αν θέλουμε να ορίσουμε τα διαγράμματα αυστηρότερα,θα γράφαμε :

   Δίνεται ένα  επίπεδο και ένα σύνολο  ν τυχαίων  σημείων  του  Σ={σ1,σ2,σ3,…,σν} (τα οποία ονομάζουμε κέντρα) ορίζουμε μια μη κενή περιοχή σημείων Ri γύρω από κάθε σi .Ορίζουμε  την απόσταση di των σημείων της περιοχής Ri από το  σi .Η περιοχή Ri ονομάζεται κελί Voronoi  όταν τα σημεία της  βρίσκονται πλησιέστερα  στο σi  από κάθε άλλο κέντρο. Το κελί Voronoi  ορίζεται ως η περιοχή σημείων  για την όποια ισχύει:

                                             Ri={xeR2/d(xi)≤ d(xj),για κάθε ij}

Όταν,βρίσκουμε για κάθε σi ένα κελί Voronoi  έχουμε σχεδιάσει το διάγραμμα.

Τέχνη
  Σε μια πρόχειρη αναζήτηση στον παντογνώστη google της φράσης «Voronoi art»  εμφανίζονται  12700000 αποτελέσματα.Πίνακες ζωγραφικής, γλυπτά,διακοσμήσεις κτισμάτων,τρισδιάστατες απεικονίσεις μέχρι σχέδια δερματοστιξίας.(tatoo στην αρχή)
Ενδεικτικά:

 -Ο Πορτογάλος εικαστικός Leonel Moura δημιούργησε μια σειρά πινάκων ζωγραφικής με τίτλο αλγόριθμοι στον Καμβά (algorithms on Canvas).O Moura χρησιμοποίησε υπολογιστή για  την κατασκευή των διαγραμμάτων Voronoi και κατόπιν χρωμάτισε τους τομείς (κελιά).Δείτε το σχήμα



-Εξωτερικός διάκοσμος του Marriot Hotel στην Φρανκφούρτη,έργο του αρχιτέκτονα Just Burgeff με τίτλο Tree Structure Canopy





- Στον 4ο κύκλο της τηλεοπτικής αστυνομικής  σειράς ΝUMB3RS ,στο επεισόδιο Μαύρος Κύκνος, ο πρωταγωνιστής χρησιμοποιεί τα διαγράμματα για να εντοπίσει τις κινήσεις ενός εγκληματία. 





Περαιτέρω αναφορές
Figuring out ,Entertaining encounters with everyday math, Nuno Crato ,εκδόσεις Springer ,2008
Mathematical Mountaintops ,J,L,Casti,εκδόσεις Oxford university press,2001
Geometry and its applications ,W.Meyer
Εξαιρετικές εργασίες  είναι οι παρακάτω
Tα διαγράμματα Voronoi.Μια εκπαιδευτική προσέγγιση για την δευτεροβάθμια εκπαίδευση,
Τσακανίκας Β, Τσαπακίδης Γ.
Ηλεκτρονικός σύνδεσμος:
Tα διαγράμματα Voronoi,Λυγάτσικας Ζήνων (http://blogs.sch.gr/zenonlig/)
Ηλεκτρονικοί σύνδεσμοι:


                          

Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου

Related Posts Plugin for WordPress, Blogger...