Vizualizare sursă pentru „Geometrie discretă și geometrie combinatorică”

[[Fișier:Unit_disk_graph.svg|dreapta|miniatura| O colecție de [[Cerc|cercuri]] și graficul corespunzător al [[Grafic disc unitate|discului de unitate]]]]
'''Geometria discretă''' și '''geometria combinatorică''' sunt ramuri ale [[Geometrie|geometriei]] care studiază proprietățile [[Combinatorică|combinatorii]] și metodele constructive ale obiectelor geometrice [[Matematică discretă|discrete]]. Majoritatea întrebărilor din geometria discretă implică [[Mulțime finită|mulțimi finite]] sau discrete de obiecte geometrice de bază, cum ar fi [[Punct (geometrie)|puncte]], [[Dreaptă|drepte]], [[Plan (geometrie)|plane]], [[cerc]]uri, [[Sferă|sfere]], [[Poligon|poligoane]] și așa mai departe. Subiectul se concentrează pe proprietățile combinatorii ale acestor obiecte, cum ar fi modul în care se [[Intersecție (matematică)|intersectează]] reciproc sau modul în care pot fi aranjate pentru a acoperi un obiect mai mare.

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

== Istorie ==
Deși [[Poliedru|poliedrele]] și [[teselare |teselările]] au fost studiate de mulți ani de oameni precum [[Johannes Kepler|Kepler]] și [[Augustin Louis Cauchy|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 [[Axel Thue|Thue]], [[Configurare proiectivă|configurațiile proiective]] de Reye și [[Ernst Steinitz|Steinitz]], [[geometria numerelor]] de Minkowski și [[Teorema celor patru culori|colorarea hărților]] de Tait, Heawood și [[Hugo Hadwiger|Hadwiger]].

[[László Fejes Tóth]], [[Harold Scott MacDonald Coxeter|HSM Coxeter]] și [[Paul Erdős]], au pus bazele ''geometriei discrete''.<ref name="Intuitive">{{Citation|last=Pach|first=János|title=Intuitive Geometry, in Memoriam László Fejes Tóth|url=http://www.renyi.hu/conferences/intuitiv_geometry/|year=2008|publisher=Alfréd Rényi Institute of Mathematics|displayauthors=etal|author-link=}}</ref> <ref>
{{Citation|last=Katona|first=G. O. H.|title=Laszlo Fejes Toth – Obituary|date=|url=|volume=42|issue=2|pages=113|year=2005|orig-year=|periodical=Studia Scientiarum Mathematicarum Hungarica|jstor=|author-link=|author-link2=}}
</ref> <ref name="DiscreteGeom1">
{{Citation|last=Bárány|first=Imre|title=A Panorama of Hungarian Mathematics in the Twentieth Century, I|url=|pages=431–441|year=2010|editor-last=Horváth|editor-first=János|contribution=Discrete and convex geometry|contribution-url=|place=New York|publisher=Springer|isbn=9783540307211|id=|author-link=Imre Bárány|author-link2=}}
</ref>

== 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 ([[apeirotop]]uri și [[teselare|teselări]]), precum și politopuri abstracte.

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

* [[Combinatorică poliedrică]]
* [[Politop întreg|Politopuri întregi]]
* [[Polinom Ehrhart|Polinoame Ehrhart]]
* [[Teorema lui Pick]]
* [[Conjectura lui Hirsch]]

=== Împachetări, acoperiri și pavări ===
[[Probleme de împachetare |Împachetările]], acoperirile și [[pavare|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 [[Varietate (geometrie)|colector]].
O ''ambalare a sferelor'' este un aranjament de [[Sferă|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]] [[spațiu tridimensional|tridimensional]]. Cu toate acestea, [[Problemă de împachetare|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 [[Hipersferă|hipersferică]] în dimensiuni superioare) sau în spațiile [[Geometrii neeuclidiene|neeuclidiene]], cum ar fi [[spațiu hiperbolic|spațiul hiperbolic]].

O ''teselare" a unei suprafețe plane este pavarea unui [[Plan (geometrie)|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ă ===
[[Fișier:Structural_rigidity_basic_examples.svg|miniatura|Grafurile sunt desenate ca tije conectate prin balamale rotative. [[Graful ciclului]] C<sub>4</sub> desenat ca un pătrat poate fi înclinat de forța albastră într-un paralelogram, deci este un graf flexibil. K<sub>3</sub>, desenat ca un triunghi, nu poate fi modificat de nicio forță care i se aplică, deci este un graf rigid]]
''[[Rigiditatea structurală]]'' este o [[Combinatorică|teorie combinatorie]] interdisciplinară de [[mecanică]] și geometrie discretă pentru prezicerea flexibilității ansamblurilor formate din corpuri rigide conectate prin [[Legătură (mecanică)|legături]] sau [[Balama|balamale]] flexibile.

Subiectele din acest domeniu includ:

* [[Teorema lui Cauchy (geometrie)|Teorema lui Cauchy]]
* [[Poliedru flexibil|Poliedre flexibile]]

=== Structuri de incidență ===
[[Fișier:Fano_plane_with_nimber_labels.svg|miniatura|Șapte puncte sunt elemente ale de șapte linii în [[plan Fano |planul Fano]], un exemplu de structură de incidență]]
Structurile de incidență generalizează planurile (cum ar fi planurile [[Plan afin (geometrie) |afine]], [[Plan proiectiv|proiective]] și [[Plan Möbius|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 [[Geometrie finită|geometrii finite]].

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

: <math>C=(P,L,I).\,</math>

unde ''P'' este un set de puncte, ''L'' este un set de [[linie |linii]] și <math>I \subseteq P \times L</math> este relația de [[Incidență (geometrie)|incidență]]. Elementele <math>I</math> se numesc ''indicatori''. Dacă

: <math>(p,l) \in I,</math>

se spune că punctul ''p'' „se află pe linia <math>l</math>” .

Subiectele din acest domeniu includ:

* [[Configurare (geometrie)|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 [[Graf orientat|grafurilor orientate]] și ale aranjamentelor vectorilor într-un [[spațiu vectorial]] peste un [[câmp ordonat]] (în special pentru [[spațiu vectorial ordonat|spațiile vectoriale parțial ordonate]]).<ref>[[Rockafellar]] 1969. Björner et alia, Chapters 1-3. Bokowski, Chapter 1. Ziegler, Chapter 7.</ref> Prin comparație, un [[matroid]] obișnuit (adică neorientat) abstractizeaza [[liniar independență|dependența]] de proprietăți care sunt comune atât [[graf]]urilor, care nu sunt ''orientate'' în mod necesar, și aranjamente de vectori peste [[Corp (matematică)|câmpuri]], care nu sunt ''ordonate'' în mod necesar.<ref>Björner et alia, Chapters 1-3. Bokowski, Chapters 1-4.</ref><ref>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.</ref>

=== Teoria grafurilor geometrice ===
Un '''grafic geometric''' este un [[graf]] în care [[Nod (teoria grafurilor)|nodurile]] sau liniile sunt asociate cu obiecte geometrice. Exemplele includ grafurile euclidiene, 1-scheletul unui poliedru sau politop, [[Graf de intersecție|grafurile de intersecție]] și [[Graf de vizibilitate|grafurile de vizibilitate]].

Subiectele din acest domeniu includ:

* [[Desen grafic]]
* [[Graf poliedric]]
* [[Diagrama Voronoi|Diagramele Voronoi]] și [[Triangulație Delaunay|triangulația Delaunay]]

=== Complexe simpliciale ===
Un ''[[complex simplicial]]'' este un [[spațiu topologic]] de un anumit tip, construit prin „lipirea” de [[Punct (geometrie)|puncte]], [[Segment (geometrie)|segmente de linie]], [[Triunghi|triunghiuri]] și [[simplex]]uri ''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 [[Graf Kneser|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]]
* [[Hartă regulată (teoria grafurilor)|Hărți regulate]]

=== Rețele și grupuri discrete ===
Un ''grup discret'' este un [[Grup (matematică)|grup]] ''G'' având o [[spațiu discret|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 de subspațiu|topologie relativă]] este cea discretă. De exemplu, [[Număr întreg|numerele întregi]], '''Z''', formează un subgrup discret al [[Număr real|realilor]], '''R''' (cu [[Spațiu metric|topologia metrică]] standard), însă [[Număr rațional|numerele raționale]], '''Q''', nu.

O ''latice'' într-un [[grup topologic]] [[compact local]] este un [[grup discret |subgrup discret]] cu proprietatea că [[spațiu topologic cât |spațiul topologic cât]] are o [[măsură invariantă]] finită. În cazul special al subgrupurilor lui '''R'''<sup>''n''</sup>, 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 [[Armand Borel|Borel]], [[Harish-Chandra]], [[George Mostow|Mostow]], [[Tsuneo Tamagawa|Tamagawa]], [[MS Raghunathan]], [[Grigory Margulis|Margulis]], [[Robert Zimmer (matematician)|Zimmer]] obținute din anii 1950 până în anii 1970 au oferit exemple și au generalizat o mare parte a teoriei la stabilirea [[Grup Lie|grupurilor]] [[grup nilpotent|nilpotente]] [[Grup Lie|Lie]] și a [[Grup algebric semisimplu|grupurilor algebrice semisimple]] pe un [[câmp local]]. În anii 1990, [[Hyman Bass|Bass]] și [[Alexander Lubotzky|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 [[spațiu discret|discrete]] (de obicei seturi de puncte discrete) considerate a fi modele digitizate sau imagini ale obiectelor din [[Spațiu euclidian|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 [[Grafică raster|raster]] a unui computer sau în ziare sunt de fapt imagini [[Date digitale|digitale]].

Principalele sale domenii de aplicare sunt [[Grafică digitală|grafica computerizată]] și [[Analiza imaginii|analiza imaginilor]].<ref>See [https://www.springer.com/us/book/9783319120980 Li Chen, Digital and discrete geometry: Theory and Algorithms, Springer, 2014.]</ref>

=== Geometrie diferențială discretă ===
''Geometria diferențială discretă'' este studiul omologilor discreți ai noțiunilor din [[Geometrie diferențială|geometria diferențială]]. În loc de curbe și suprafețe netede, există [[Poligon|poligoane]], [[Plasă|ochiuri]] și [[Complex simplicial|complexe simpliciale]]. Este utilizat în studiul [[Grafică digitală|graficii computerizate]] și a [[Combinatorică topologică|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 ==
{{listănote|2}}

== Lectură suplimentară ==
* {{en icon}} {{Citat carte|nume=Bezdek, András|titlu=Discrete geometry: in honor of W. Kuperberg's 60th birthday|editură=Marcel Dekker|locul-publicării=New York, N.Y|an=2003|isbn=0-8247-0968-3}}
* {{en icon}} {{Citat carte|nume=[[Károly Bezdek|Bezdek, Károly]]|titlu=Classical Topics in Discrete Geometry|editură=Springer|locul-publicării=New York, N.Y|an=2010|isbn=978-1-4419-0599-4}}
* {{en icon}} {{Citat carte|nume=[[Károly Bezdek|Bezdek, Károly]]|titlu=Lectures on Sphere Arrangements - the Discrete Geometric Side|editură=Springer|locul-publicării=New York, N.Y|an=2013|isbn=978-1-4614-8117-1}}
* {{en icon}} {{Citat carte|nume=Bezdek|prenume=Károly|nume2=Deza|prenume2=Antoine|nume3=Ye|prenume3=Yinyu|legătură-autor=Károly Bezdek|titlu=Discrete Geometry and Optimization|editură=Springer|locul-publicării=New York, N.Y|an=2013|isbn=978-3-319-00200-2}}
* {{en icon}} {{Citat carte|nume=Brass|prenume=Peter|nume2=Moser|prenume2=William|nume3=Pach|prenume3=János|legătură-autor3=János Pach|titlu=Research problems in discrete geometry|editură=Springer|locul-publicării=Berlin|an=2005|isbn=0-387-23815-8}}
* {{en icon}} {{Citat carte|nume=Pach|prenume=János|legătură-autor=János Pach|nume2=Agarwal|prenume2=Pankaj K.|titlu=Combinatorial geometry|url=https://archive.org/details/combinatorialgeo0000pach|editură=Wiley-Interscience|locul-publicării=New York|an=1995|isbn=0-471-58890-3}}
* {{en icon}} {{Citat carte|nume=[[Jacob E. Goodman|Goodman, Jacob E.]] and O'Rourke, Joseph|titlu=Handbook of Discrete and Computational Geometry, Second Edition|editură=Chapman & Hall/CRC|locul-publicării=Boca Raton|an=2004|isbn=1-58488-301-4}}
* {{en icon}} {{Citat carte|nume=Gruber|prenume=Peter M.|legătură-autor=Peter M. Gruber|titlu=Convex and Discrete Geometry|editură=Springer|locul-publicării=Berlin|an=2007|isbn=3-540-71132-5}}
* {{en icon}} {{Citat carte|nume=Matoušek, Jiří|titlu=Lectures on discrete geometry|editură=Springer|locul-publicării=Berlin|an=2002|isbn=0-387-95374-4}}
* {{en icon}} {{Citat carte|nume=[[Vladimir Boltyanski]], [[Horst Martini]], Petru S. Soltan|titlu=Excursions into Combinatorial Geometry|editură=Springer|an=1997|isbn=3-540-61341-2}}

[[Categorie:GIS]]
[[Categorie:Geometrie discretă| ]]
[[Categorie:Topologie]]