Διακριτή γεωμετρία

Μια συλλογή κύκλων και το αντίστοιχο γράφημα του μοναδιαίου δίσκου

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

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

Ιστορία

Παρόλο που τα πολύεδρα και τη Ψηφιδοθέτηση είχαν μελετηθεί επί σειρά ετών από ανθρώπους όπως ο Κέπλερ και ο Κωσύ, η σύγχρονη διακριτή γεωμετρία έχει τις ρίζες της στα τέλη του 19ου αιώνα. Τα πρώτα θέματα που μελετήθηκαν ήταν: η πυκνότητα των κυκλικών συσκευασιών από τον Άξελ Τούε, οι προβολικές διαμορφώσεις από τους Ρέι και Στάινιτζ, η γεωμετρία των αριθμών από τον Μινκόφσκι και οι χρωματισμοί χαρτών από τους Τέιτ, Χέαγουντ και Χάντγουιγκερ.

Ο Λάσλο Φέγες Τοτ, ο Χ.Σ.Μ. Κόξετερ και ο Πολ Έρντος έθεσαν τα θεμέλια της διακριτής γεωμετρίας^[1][2][3]

Θεματολογία

Πολύεδρα και πολύτοπα

Κύρια άρθρα: Πολύεδρο και Γεωμετρικό πολύτοπο

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

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

• Πολυεδρική συνδυαστική^[4]
• Πολυτόπα πλέγματος^[5]
• Πολυώνυμα Έρχαρτ^[6]
• Θεώρημα του Πικ^[7]
• Εικασία Χερς^[8]
• Αδιαφανές σύνολο^[9]

Συσκευασίες, καλύψεις και επιστρώσεις

Κύριο άρθρο: Ψηφιδοθέτηση

Οι συσκευασίες, οι καλύψεις και οι πλακοστρώσεις είναι όλοι τρόποι διευθέτησης ομοιόμορφων αντικειμένων (συνήθως κύκλων, σφαιρών ή πλακιδίων) με κανονικό τρόπο σε ένα επιφάνεια ή πολλαπλότητα.

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

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

Συγκεκριμένα θέματα σε αυτόν τον τομέα περιλαμβάνουν:

• Συσκευασίες κύκλου
• Σφαιρικές συσκευασίες^[10]
• Εικασία του Κέπλερ^[11]
• Οιονεί κρύσταλλοι^[12]
• Περιοδικές πλακοστρώσεις
• Περιοδικός γράφος^[13]
• Κανόνες πεπερασμένης υποδιαίρεσης

Δομική ακαμψία και ευελιξία

Οι γραφικές παραστάσεις απεικονίζονται με ράβδους που συνδέονται με περιστρεφόμενους κρίκους. Το γράφημα κύκλου

Η δομική ακαμψία είναι μια συνδυαστική θεωρία για την πρόβλεψη της ευκαμψίας των συνόλων που σχηματίζονται από άκαμπτα σώματα που συνδέονται με εύκαμπτους συνδέσμους ή αρθρώσεις.

Τα θέματα που αφορούν αυτόν τον τομέα περιλαμβάνουν:

• Θεώρημα του Cauchy
• Εύκαμπτα πολύεδρα

Δομή πρόσπτωσης

Επτά σημεία είναι στοιχεία επτά γραμμών στο επίπεδο Φανό, ένα παράδειγμα δομής πρόσπτωσης.

Οι δομές πρόσπτωσης γενικεύουν τα επίπεδα (όπως τα affine, προβολικά και Möbius πεδία), όπως φαίνεται από τους αξιωματικούς ορισμούς τους. Οι δομές πρόσπτωσης γενικεύουν επίσης τα ανάλογα υψηλότερων διαστάσεων και οι πεπερασμένες δομές καλούνται μερικές φορές πεπερασμένες γεωμετρίες.

Τυπικά, μια δομή επίπτωσης είναι μια τριάδα

${\displaystyle C=(P,L,I).\,}$

όπου P είναι ένα σύνολο από "σημεία", L είναι ένα σύνολο από "γραμμές" και ${\displaystyle I\subseteq P\times L}$ είναι η συσχέτιση επίπτωσης. Τα στοιχεία του ${\displaystyle I}$ ονομάζονται σημαίες. Αν

${\displaystyle (p,l)\in I,}$

λέμε ότι το σημείο p "βρίσκεται" στην ευθεία ${\displaystyle l}$.

Τα θέματα σε αυτόν τον τομέα περιλαμβάνουν:

• Διαμόρφωση (γεωμετρία)
• Διάταξη γραμμών
• Διάταξη υπερεπιπέδων
• Κτίριο (μαθηματικά)^[14][15]

Προσανατολισμένα μητροειδή

Ένα προσανατολισμένο ματροειδές είναι μια μαθηματική δομή που αφηρημένα παρουσιάζει τις ιδιότητες των κατευθυνόμενων γραφημάτων και των διατάξεων διανυσμάτων σε ένα διανυσματικό χώρο πάνω από ένα διατεταγμένο πεδίο (ιδιαίτερα για μερικώς διατεταγμένους διανυσματικούς χώρους)^[16] Συγκριτικά, ένα συνηθισμένο (δηλαδή μη προσανατολισμένο) ματροειδές αφηρημένα παρουσιάζει τις ιδιότητες εξάρτησης που είναι κοινές τόσο για τα γραφήματα, τα οποία δεν είναι απαραίτητα κατευθυνόμενα, όσο και για τις διατάξεις των διανυσμάτων πάνω από πεδία, τα οποία δεν είναι απαραίτητα διατεταγμένα^[17][18].

Γεωμετρική θεωρία γραφημάτων

Ένας γεωμετρικός γράφος είναι ένας γράφος στον οποίο οι κορυφές ή οι ακμές συνδέονται με γεωμετρικά αντικείμενα. Παραδείγματα περιλαμβάνουν τους ευκλείδειους γράφους, το 1-σκελετό ενός πολυέδρου ή πολυτόπου, τους γράφους μοναδιαίων δίσκων και τους γράφους ορατότητας.

Τα θέματα σε αυτόν τον τομέα περιλαμβάνουν:

• Σχεδίαση γραφημάτων
• Πολυεδρικοί γράφοι
• Τυχαία γεωμετρικά γραφήματα
• Διαγράμματα Βορονόι και τριγωνισμοί Ντελονέι

Σύμπλεγμα (Simpliciale complex)

Ένα σύμπλεγμα (Simpliciale complex)^[19] είναι ένας τοπολογικός χώρος ενός συγκεκριμένου είδους, που κατασκευάζεται με "συγκόλληση" σημείων, τμημάτων ευθείας, τριγώνων και των n-διάστατων ομοιωμάτων τους (βλ. εικόνα). Τα Συμπλέγματα (Simpliciale complex) δεν πρέπει να συγχέονται με την πιο αφηρημένη έννοια του απλοϊκού συνόλου που εμφανίζεται στη σύγχρονη απλοϊκή θεωρία ομοτοπίας. Το καθαρά συνδυαστικό αντίστοιχο ενός συμπλέγματος (Simpliciale complex) είναι ένα αφηρημένο σύμπλεγμα (Simpliciale complex). Βλέπε επίσης τυχαία γεωμετρικά συμπλέγματα.

Τοπολογική συνδυαστική

Ο κλάδος της συνδυαστικής τοπολογίας χρησιμοποίησε συνδυαστικές έννοιες στην τοπολογία και στις αρχές του 20ού αιώνα αυτό μετατράπηκε στο πεδίο της αλγεβρικής τοπολογίας.

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

Τα θέματα σε αυτόν τον τομέα περιλαμβάνουν:

• Λήμμα του Σπέρνερ
• Κανονικοί χάρτες

Πλέγματα και διακριτές ομάδες

Μια διακριτή ομάδα είναι μια ομάδα G εξοπλισμένη με τη διακριτή τοπολογία. Με αυτή την τοπολογία, η G γίνεται μια τοπολογική ομάδα. Μια διακριτή υποομάδα μιας τοπολογικής ομάδας G είναι μια υποομάδα H της οποίας η σχετική τοπολογία είναι η διακριτή. Παραδείγματος χάριν, οι ακέραιοι αριθμοί, Z, αποτελούν διακριτή υποομάδα των πραγματικών αριθμών, R (με την τυπική μετρική τοπολογία), αλλά οι ρητοί αριθμοί, Q, αποκλείονται.

Ένα πλέγμα σε μια τοπικά συμπαγή τοπολογική ομάδα είναι μια διακριτή υποομάδα με την ιδιότητα ότι ο πηλίκο χώρος έχει πεπερασμένο αναλλοίωτο μέτρο. Στην ειδική περίπτωση των υποομάδων του Rⁿ, αυτό ισοδυναμεί με τη συνήθη γεωμετρική έννοια του πλέγματος, και τόσο η αλγεβρική δομή των πλεγμάτων όσο και η γεωμετρία του συνόλου όλων των πλεγμάτων είναι σχετικά καλά κατανοητές. Τα βαθιά αποτελέσματα των Μπορέλ, Χάρις-Τσάντρα, Μόστοου, Ταμαγκάουα, Μ. Σ. Ραγκουνάθαν, Μαργκούλις, Τσίμερ που προέκυψαν από τη δεκαετία του 1950 έως τη δεκαετία του 1970 παρείχαν παραδείγματα και γενίκευσαν μεγάλο μέρος της θεωρίας στο περιβάλλον των μηδενικών ομάδων Lie και των ημιμονοσήμαντων αλγεβρικών ομάδων πάνω από ένα τοπικό πεδίο. Στη δεκαετία του 1990, οι Μπας και Λουμπότζκι ξεκίνησαν τη μελέτη των δενδροειδών πλεγμάτων, η οποία παραμένει ενεργός ερευνητικός τομέας.

Τα θέματα σε αυτόν τον τομέα περιλαμβάνουν:

• Ομάδες αναστοχασμού
• Ομάδες τριγώνων

Ψηφιακή γεωμετρία

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

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

Οι κύριοι τομείς εφαρμογής της είναι τα γραφικά υπολογιστών και η ανάλυση εικόνων^[20].

Διακριτή διαφορική γεωμετρία

Η διακριτή διαφορική γεωμετρία είναι η μελέτη των διακριτών αντίστοιχων εννοιών της διαφορικής γεωμετρίας. Αντί για λείες καμπύλες και επιφάνειες, υπάρχουν πολύγωνα, πλέγματα και απλοποιημένα σύμπλοκα. Χρησιμοποιείται στη μελέτη των γραφικών υπολογιστών και της τοπολογικής συνδυαστικής.

Τα θέματα αυτής της περιοχής περιλαμβάνουν:

• Διακριτός τελεστής Λαπλάς
• Διακριτός εξωτερικός λογισμός
• Διακριτός λογισμός
• Διακριτή θεωρία Μορς
• Τοπολογική συνδυαστική
• Ανάλυση φασματικού σχήματος
• Αφηρημένη διαφορική γεωμετρία
• Μελέτη των φράκταλ

Βιβλιογραφία

• Bezdek, András (2003). Discrete geometry: in honor of W. Kuperberg's 60th birthday. New York, N.Y: Marcel Dekker. ISBN 0-8247-0968-3. 
• Bezdek, Károly (2010). Classical Topics in Discrete Geometry. New York, N.Y: Springer. ISBN 978-1-4419-0599-4. 
• Bezdek, Károly (2013). Lectures on Sphere Arrangements - the Discrete Geometric Side. New York, N.Y: Springer. ISBN 978-1-4614-8117-1. 
• Bezdek, Károly· Deza, Antoine· Ye, Yinyu (2013). Discrete Geometry and Optimization. New York, N.Y: Springer. ISBN 978-3-319-00200-2. 
• Brass, Peter· Moser, William· Pach, János (2005). Research problems in discrete geometry. Berlin: Springer. ISBN 0-387-23815-8. 
• Pach, János· Agarwal, Pankaj K. (1995). Combinatorial geometry. New York: Wiley-Interscience. ISBN 0-471-58890-3. 
• Goodman, Jacob E. and O'Rourke, Joseph (2004). Handbook of Discrete and Computational Geometry, Second Edition. Boca Raton: Chapman & Hall/CRC. ISBN 1-58488-301-4. 
• Gruber, Peter M. (2007). Convex and Discrete Geometry. Berlin: Springer. ISBN 978-3-540-71132-2. 
• Matoušek, Jiří (2002). Lectures on discrete geometry. Berlin: Springer. ISBN 0-387-95374-4. 
• en:Vladimir Boltyanski, en:Horst Martini, Petru S. Soltan (1997). Excursions into Combinatorial Geometry. Springer. ISBN 3-540-61341-2. 

Δείτε επίσης

• Διακριτά μαθηματικά
• Πολ Έρντος

Παραπομπές

1. Pach, János (2008), Intuitive Geometry, in Memoriam László Fejes Tóth, Alfréd Rényi Institute of Mathematics, http://www.renyi.hu/conferences/intuitiv_geometry/ 
2. Katona, G. O. H. (2005), «Laszlo Fejes Toth – Obituary», Studia Scientiarum Mathematicarum Hungarica 42 (2): 113 
3. Bárány, Imre (2010), «Discrete and convex geometry», στο: Horváth, János, επιμ., A Panorama of Hungarian Mathematics in the Twentieth Century, I, New York: Springer, σελ. 431–441, ISBN 9783540307211 
4. Cook, William J.· Seymour, Paul D. (1990). Polyhedral Combinatorics: Proceedings of a DIMACS Workshop : June 12-16, 1989. American Mathematical Society. ISBN 978-0-8218-6591-0. 
5. «LatticePolytopes -- for computations with lattice polytopes». macaulay2.com. Ανακτήθηκε στις 17 Ιανουαρίου 2024. 
6. Diaz, Ricardo; Robins, Sinai (1997). «The Ehrhart Polynomial of a Lattice Polytope». Annals of Mathematics 145 (3): 503–518. doi:10.2307/2951842. ISSN 0003-486X. https://www.jstor.org/stable/2951842. 
7. Grunbaum, Branko; Shephard, G. C. (1993). «Pick's Theorem». The American Mathematical Monthly 100 (2): 150–161. doi:10.2307/2323771. ISSN 0002-9890. https://www.jstor.org/stable/2323771. 
8. «Problem». www.sfu.ca. Ανακτήθηκε στις 17 Ιανουαρίου 2024. 
9. Bagemihl, F. (1959-01). «Some opaque subsets of a square.». Michigan Mathematical Journal 6 (2): 99–103. doi:10.1307/mmj/1028998183. ISSN 0026-2285. https://projecteuclid.org/journals/michigan-mathematical-journal/volume-6/issue-2/Some-opaque-subsets-of-a-square/10.1307/mmj/1028998183.full. 
10. Leech, John (1967-01). «Notes on Sphere Packings» (στα αγγλικά). Canadian Journal of Mathematics 19: 251–267. doi:10.4153/CJM-1967-017-0. ISSN 0008-414X. https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/notes-on-sphere-packings/E926AB3EA0CB315FB5FAEFDE65719E79. 
11. «Kepler's conjecture | mathematics | Britannica». www.britannica.com (στα Αγγλικά). Ανακτήθηκε στις 17 Ιανουαρίου 2024. 
12. «Τα αραβουργήματα της φύσης». physicsgg. 15 Οκτωβρίου 2011. Ανακτήθηκε στις 17 Ιανουαρίου 2024. 
13. «Periodic graph (graph theory) | Semantic Scholar». www.semanticscholar.org (στα Αγγλικά). Ανακτήθηκε στις 17 Ιανουαρίου 2024. 
14. «INTRODUCTION TO BRUHAT-TITS BUILDINGS - UNIVERSITY OF CHICAGO» (PDF). 
15. «Tits building - Encyclopedia of Mathematics». encyclopediaofmath.org. Ανακτήθηκε στις 17 Ιανουαρίου 2024. 
16. Rockafellar 1969. Björner et alia, Chapters 1-3. Bokowski, Chapter 1. Ziegler, Chapter 7.
17. Björner et alia, Chapters 1-3. Bokowski, Chapters 1-4.
18. Because matroids and oriented matroids are abstractions of other mathematical abstractions, nearly all the relevant books are written for mathematical scientists rather than for the general public. For learning about oriented matroids, a good preparation is to study the textbook on linear optimization by Nering and Tucker, which is infused with oriented-matroid ideas, and then to proceed to Ziegler's lectures on polytopes.
19. «1.2. Simplices και Συμπλέγματα - Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης» (PDF). 
20. See Li Chen, Digital and discrete geometry: Theory and Algorithms, Springer, 2014.