Geometrie discretă și geometrie combinatorică

Geometria discretă și geometria combinatorică sunt ramuri ale geometriei care studiază proprietățile combinatorii și metodele constructive ale obiectelor geometrice discrete. Majoritatea întrebărilor din geometria discretă implică mulțimi finite sau discrete de obiecte geometrice de bază, cum ar fi puncte, drepte, plane, cercuri, sfere, poligoane și așa mai departe. Subiectul se concentrează pe proprietățile combinatorii ale acestor obiecte, cum ar fi modul în care se intersectează reciproc sau modul în care pot fi aranjate pentru a acoperi un obiect mai mare.

O colecție de cercuri și graficul corespunzător al discului de unitate

Geometria discretă are o suprapunere mare cu geometria convexă și geometria algoritmică și este strâns legată de subiecte precum geometria finită, optimizarea combinatorie, geometria digitală, geometria diferențială discretă, teoria grafurilor geometrice, geometria torică și topologia combinatorie.

Istorie

Deși poliedrele și teselările au fost studiate de mulți ani de oameni precum Kepler și Cauchy, geometria discretă modernă își are originile la sfârșitul secolului al XIX-lea. Temele studiate timpuriu au fost: densitatea pachetelor de cercuri de Thue, configurațiile proiective de Reye și Steinitz, geometria numerelor de Minkowski și colorarea hărților de Tait, Heawood și Hadwiger.

László Fejes Tóth, HSM Coxeter și Paul Erdős, au pus bazele geometriei discrete.^{[1] [2] [3]}

Subiecte

Poliedre și politopuri

Un politop este un obiect geometric cu fețe plane, care există în orice număr de dimensiuni. Un poligon este un politop în două dimensiuni, un poliedru în trei dimensiuni și așa mai departe în dimensiuni superioare (cum ar fi un 4-politop în patru dimensiuni). Unele teorii generalizează în continuare ideea de a include obiecte, cum ar fi politopuri infinite (apeirotopuri și teselări), precum și politopuri abstracte.

Următoarele sunt câteva dintre aspectele politopurilor studiate în geometria discretă:

• Combinatorică poliedrică
• Politopuri întregi
• Polinoame Ehrhart
• Teorema lui Pick
• Conjectura lui Hirsch

Împachetări, acoperiri și pavări

Împachetările, acoperirile și pavările sunt toate moduri de a aranja obiecte uniforme (de obicei cercuri, sfere sau plăci) în mod regulat pe o suprafață sau pe un colector. O ambalare a sferelor este un aranjament de sfere care nu se intersectează într-un spațiu care le conține. Sferele luate în considerare sunt de obicei toate de dimensiuni identice, iar spațiul este de obicei spațiu euclidian tridimensional. Cu toate acestea, problemele de împachetare ale sferelor pot fi generalizate pentru a lua în considerare sferele inegale, spațiul euclidian n-dimensional (unde problema devine împachetare în cerc în două dimensiuni respectiv împachetare hipersferică în dimensiuni superioare) sau în spațiile neeuclidiene, cum ar fi spațiul hiperbolic.

O teselare" a unei suprafețe plane este pavarea unui plan folosind una sau mai multe forme geometrice, numite plăci, fără suprapuneri și fără goluri. În matematică, mozaicările pot fi generalizate la dimensiuni superioare.

Subiectele specifice din acest domeniu includ:

• Împachetarea cercurilor
• Împachetarea sferelor
• Conjectura Kepler
• Cvasicristale
• Pavare aperiodică
• Graf periodic
• Regula subdivizării finite

Rigiditate și flexibilitate structurală

Grafurile sunt desenate ca tije conectate prin balamale rotative. Graful ciclului C₄ desenat ca un pătrat poate fi înclinat de forța albastră într-un paralelogram, deci este un graf flexibil. K₃, desenat ca un triunghi, nu poate fi modificat de nicio forță care i se aplică, deci este un graf rigid

Rigiditatea structurală este o teorie combinatorie interdisciplinară de mecanică și geometrie discretă pentru prezicerea flexibilității ansamblurilor formate din corpuri rigide conectate prin legături sau balamale flexibile.

Subiectele din acest domeniu includ:

• Teorema lui Cauchy
• Poliedre flexibile

Structuri de incidență

Șapte puncte sunt elemente ale de șapte linii în planul Fano, un exemplu de structură de incidență

Structurile de incidență generalizează planurile (cum ar fi planurile afine, proiective și Möbius) așa cum se poate vedea din definițiile lor axiomatice. Analogiile din structurile de incidență se pot generaliza în dimensiuni superioare, iar structurile finite sunt uneori numite geometrii finite.

În mod formal, o structură de incidență este un triplet

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

unde P este un set de puncte, L este un set de linii și ${\displaystyle I\subseteq P\times L}$ este relația de incidență. Elementele ${\displaystyle I}$ se numesc indicatori. Dacă

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

se spune că punctul p „se află pe linia ${\displaystyle l}$” .

Subiectele din acest domeniu includ:

• Configurări
• Aranjament de linii
• Aranjament de hiperplane
• Imobil Bruhat-Tits

Matroizi orientați

Un matroid orientat este o structură matematică care abstractizează proprietățile grafurilor orientate și ale aranjamentelor vectorilor într-un spațiu vectorial peste un câmp ordonat (în special pentru spațiile vectoriale parțial ordonate).^[4] Prin comparație, un matroid obișnuit (adică neorientat) abstractizeaza dependența de proprietăți care sunt comune atât grafurilor, care nu sunt orientate în mod necesar, și aranjamente de vectori peste câmpuri, care nu sunt ordonate în mod necesar.^[5][6]

Teoria grafurilor geometrice

Un grafic geometric este un graf în care nodurile sau liniile sunt asociate cu obiecte geometrice. Exemplele includ grafurile euclidiene, 1-scheletul unui poliedru sau politop, grafurile de intersecție și grafurile de vizibilitate.

Subiectele din acest domeniu includ:

• Desen grafic
• Graf poliedric
• Diagramele Voronoi și triangulația Delaunay

Complexe simpliciale

Un complex simplicial este un spațiu topologic de un anumit tip, construit prin „lipirea” de puncte, segmente de linie, triunghiuri și simplexuri n- dimensionale (vezi ilustrația). Complexele simpliciale nu trebuie confundate cu noțiunea mai abstractă a unui set simplicial care apare în teoria modernă a homotopiei simpliciale. Omologul pur combinatoriu la un complex simplicial este un complex simplicial abstract .

Combinatorică topologică

Disciplina combinatoricii topologice a folosit concepte ale combinatoricii în topologie și la începutul secolului al XX-lea, aceasta s-a transformat în domeniul topologie algebrică.

În 1978 situația a fost inversată — metodele din topologia algebrică au fost folosite pentru a rezolva o problemă în combinatorică — când László Lovász a demonstrat conjectura Kneser, începând astfel noul studiu al combinatoricii topologice. Demonstrația lui Lovász a folosit teorema Borsuk-Ulam; această teoremă are un rol important în acest nou domeniu. Această teoremă are mai multe versiuni echivalente și analogii și a fost utilizată în studiul problemelor de împărțire echitabilă.

Subiectele din acest domeniu includ:

• Lema lui Sperner
• Hărți regulate

Rețele și grupuri discrete

Un grup discret este un grup G având o topologie discretă. Cu această topologie, G devine un grup topologic. Un subgrup discret al unui grup topologic G este un subgrup H a cărui topologie relativă este cea discretă. De exemplu, numerele întregi, Z, formează un subgrup discret al realilor, R (cu topologia metrică standard), însă numerele raționale, Q, nu.

O latice într-un grup topologic compact local este un subgrup discret cu proprietatea că spațiul topologic cât are o măsură invariantă finită. În cazul special al subgrupurilor lui Rⁿ, aceasta se ridică la noțiunea geometrică obișnuită a unei rețele și atât structura algebrică a rețelelor, cât și geometria totalității tuturor rețelelor sunt relativ bine înțelese. Rezultatele profunde ale lui Borel, Harish-Chandra, Mostow, Tamagawa, MS Raghunathan, Margulis, Zimmer obținute din anii 1950 până în anii 1970 au oferit exemple și au generalizat o mare parte a teoriei la stabilirea grupurilor nilpotente Lie și a grupurilor algebrice semisimple pe un câmp local. În anii 1990, Bass și Lubotzky au inițiat studiul structurii arborilor, care rămâne o zonă activă de cercetare.

Subiectele din acest domeniu includ:

• Grup de reflexie
• Grup triunghiular

Geometrie digitală

Geometria digitală se ocupă de seturi discrete (de obicei seturi de puncte discrete) considerate a fi modele digitizate sau imagini ale obiectelor din spațiul euclidian 2D sau 3D.

Pur și simplu, digitizarea înseamnă înlocuirea unui obiect cu un set discret de puncte ale acestuia. Imaginile pe care le vedem pe ecranul televizorului, afișarea raster a unui computer sau în ziare sunt de fapt imagini digitale.

Principalele sale domenii de aplicare sunt grafica computerizată și analiza imaginilor.^[7]

Geometrie diferențială discretă

Geometria diferențială discretă este studiul omologilor discreți ai noțiunilor din geometria diferențială. În loc de curbe și suprafețe netede, există poligoane, ochiuri și complexe simpliciale. Este utilizat în studiul graficii computerizate și a combinatoricii topologice.

Subiectele din acest domeniu includ:

• Operator Laplace discret
• Calcul exterior discret
• Calcul discret
• Teoria Morse discretă
• Combinatorică topologică
• Analiza spectrală a formei
• Geometrie diferențială abstractă
• Analiza pe fractali

Vezi și

• Geometrie discretă și computațională (jurnal)
• Matematică discretă
• Paul Erdős

Note

1. Pach, János; et al. (2008), Intuitive Geometry, in Memoriam László Fejes Tóth, Alfréd Rényi Institute of Mathematics
2. Katona, G. O. H. (2005), „Laszlo Fejes Toth – Obituary”, Studia Scientiarum Mathematicarum Hungarica, 42 (2), p. 113
3. Bárány, Imre (2010), „Discrete and convex geometry”, În Horváth, János, A Panorama of Hungarian Mathematics in the Twentieth Century, I, New York: Springer, pp. 431–441, ISBN 9783540307211
4. Rockafellar 1969. Björner et alia, Chapters 1-3. Bokowski, Chapter 1. Ziegler, Chapter 7.
5. Björner et alia, Chapters 1-3. Bokowski, Chapters 1-4.
6. 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.
7. See Li Chen, Digital and discrete geometry: Theory and Algorithms, Springer, 2014.

Lectură suplimentară

• en 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.
• en Bezdek, Károly (2010). Classical Topics in Discrete Geometry. New York, N.Y: Springer. ISBN 978-1-4419-0599-4.
• en Bezdek, Károly (2013). Lectures on Sphere Arrangements - the Discrete Geometric Side. New York, N.Y: Springer. ISBN 978-1-4614-8117-1.
• en Bezdek, Károly; Deza, Antoine; Ye, Yinyu (2013). Discrete Geometry and Optimization. New York, N.Y: Springer. ISBN 978-3-319-00200-2.
• en Brass, Peter; Moser, William; Pach, János (2005). Research problems in discrete geometry. Berlin: Springer. ISBN 0-387-23815-8.
• en Pach, János; Agarwal, Pankaj K. (1995). Combinatorial geometry. New York: Wiley-Interscience. ISBN 0-471-58890-3.
• en 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.Mentenanță CS1: Nume multiple: lista autorilor (link)
• en Gruber, Peter M. (2007). Convex and Discrete Geometry. Berlin: Springer. ISBN 3-540-71132-5.
• en Matoušek, Jiří (2002). Lectures on discrete geometry. Berlin: Springer. ISBN 0-387-95374-4.
• en Vladimir Boltyanski, Horst Martini, Petru S. Soltan (1997). Excursions into Combinatorial Geometry. Springer. ISBN 3-540-61341-2.Mentenanță CS1: Nume multiple: lista autorilor (link)