Géométrie discrète

Un ensemble de cercles et le graphique du disque unité correspondant

La géométrie discrète et la géométrie combinatoire sont des branches de la géométrie qui étudient les propriétés combinatoires et les méthodes de construction des objets géométriques discrets . La plupart des problèmes en géométrie discrète portent sur des ensembles finis ou discrets d'objets géométriques de base, tels que les points , les droites , les plans , les cercles , les sphères , les polygones , etc. Ce domaine s'intéresse aux propriétés combinatoires de ces objets, notamment à la manière dont ils s'intersectent ou dont ils peuvent être agencés pour recouvrir un objet plus grand.

La géométrie discrète présente un large chevauchement avec la géométrie convexe et la géométrie algorithmique , et est étroitement liée à des sujets tels que la géométrie finie , l'optimisation combinatoire , la géométrie numérique , la géométrie différentielle discrète , la théorie géométrique des graphes , la géométrie torique et la topologie combinatoire .

Les polyèdres et les pavages ont été étudiés pendant de nombreuses années par des personnalités telles que Kepler et Cauchy , mais la géométrie discrète moderne trouve ses origines à la fin du XIXe siècle. Parmi les premiers sujets étudiés figuraient : la densité des empilements de cercles par Thue , les configurations projectives par Reye et Steinitz , la géométrie des nombres par Minkowski et les colorations de cartes par Tait, Heawood et Hadwiger .

László Fejes Tóth , HSM Coxeter et Paul Erdős ont posé les bases de la géométrie discrète .

Sujets

Polyèdres et polytopes

polygone est un polytope en deux dimensions, un polyèdre en trois dimensions, et ainsi de suite en dimensions supérieures (comme un 4-polytope en quatre dimensions). Certaines théories généralisent davantage cette notion pour inclure des objets tels que les polytopes non bornés ( apeirotopes et pavages ) et les polytopes abstraits .

Voici quelques aspects des polytopes étudiés en géométrie discrète :

Garnitures, revêtements et carrelages

une variété .

L' empilement de sphères est un arrangement de sphères non superposées dans un espace donné. Les sphères considérées sont généralement toutes de même taille, et l'espace est généralement l'espace euclidien tridimensionnel . Cependant, les problèmes d'empilement de sphères peuvent être généralisés pour considérer des sphères de tailles différentes, l'espace euclidien n- dimensionnel (où le problème se ramène à l'empilement de cercles en deux dimensions, ou à l'empilement d'hypersphères en dimensions supérieures) ou des espaces non euclidiens tels que l'espace hyperbolique .

Le pavage d'une surface plane consiste à recouvrir un plan d'une ou plusieurs formes géométriques, appelées tuiles, sans chevauchement ni espace vide. En mathématiques , les pavages peuvent être généralisés à des dimensions supérieures.

Les thèmes spécifiques abordés dans ce domaine comprennent :

Rigidité et flexibilité structurelles

Les graphes sont représentés comme des tiges reliées par des charnières rotatives. Le graphe cyclique C₄ _, dessiné sous forme de carré, peut être basculé par la force bleue pour former un parallélogramme ; il s'agit donc d'un graphe flexible. K₃ _, dessiné sous forme de triangle, ne peut être modifié par aucune force appliquée ; il s'agit donc d'un graphe rigide.

La rigidité structurelle est une théorie combinatoire permettant de prédire la flexibilité d'ensembles formés de corps rigides reliés par des liaisons ou des charnières flexibles .

Les sujets abordés dans ce domaine comprennent :

Structures d'incidence

Sept points sont des éléments de sept droites du plan de Fano , un exemple de structure d'incidence.

Les structures d'incidence généralisent les plans (tels que les plans affine , projectif et de Möbius ), comme le montrent leurs définitions axiomatiques. Elles généralisent également leurs analogues de dimension supérieure, et les structures finies qui en résultent sont parfois appelées géométries finies .

Formellement, une structure d'incidence est un triplet

où P est un ensemble de « points », L est un ensemble de « droites » et représente la relation d'incidence . Les éléments de sont appelés drapeaux. Si

nous disons que le point p « se trouve sur » la ligne .

Les sujets abordés dans ce domaine comprennent :

Matroïdes orientés

structure mathématique qui abstrait les propriétés des graphes orientés et des arrangements de vecteurs dans un espace vectoriel sur un corps ordonné (en particulier pour les espaces vectoriels partiellement ordonnés ). Par comparaison, un matroïde ordinaire (c'est-à-dire non orienté) abstrait les propriétés de dépendance communes aux graphes , qui ne sont pas nécessairement orientés , et aux arrangements de vecteurs sur des corps , qui ne sont pas nécessairement ordonnés .

théorie géométrique des graphes

graphe dont les sommets ou les arêtes sont associés à des objets géométriques . On peut citer comme exemples les graphes euclidiens, le 1- squelette d'un polyèdre ou d' un polytope , les graphes de disques unitaires et les graphes de visibilité .

Les sujets abordés dans ce domaine comprennent :

Complexes simpliciaux

espace topologique d'un certain type, construit en « collant » des points , des segments de droite , des triangles et leurs homologues de dimension n (voir illustration). Il ne faut pas confondre les complexes simpliciaux avec la notion plus abstraite d' ensemble simplicial, qui apparaît dans la théorie moderne de l'homotopie simpliciale. L'équivalent purement combinatoire d'un complexe simplicial est un complexe simplicial abstrait . Voir aussi les complexes géométriques aléatoires .

combinatoire topologique

topologie et, au début du XXe siècle, elle s'est transformée en domaine de la topologie algébrique .

En 1978, la situation s'est inversée : des méthodes de topologie algébrique ont été utilisées pour résoudre un problème de combinatoire . László Lovász a démontré la conjecture de Kneser , inaugurant ainsi le champ d'étude de la combinatoire topologique . La démonstration de Lovász s'appuyait sur le théorème de Borsuk-Ulam , qui conserve une place prépondérante dans ce nouveau domaine. Ce théorème possède de nombreuses versions équivalentes et analogues et a notamment été utilisé dans l'étude des problèmes de partage équitable .

Les sujets abordés dans ce domaine comprennent :

Réseaux et groupes discrets

groupe G muni de la topologie discrète . Avec cette topologie, G devient un groupe topologique . Un sous-groupe discret d'un groupe topologique G est un sous-groupe H dont la topologie relative est la topologie discrète. Par exemple, les entiers ℤ forment un sous-groupe discret des réels ℝ ( muni de la topologie métrique usuelle ) , mais les nombres rationnels ℕ ne le sont pas.

Un treillis d'un groupe topologique localement compact est un sous-groupe discret dont l' espace quotient possède une mesure invariante finie . Dans le cas particulier des sous-groupes de R<sup> ^n</sup> , cela correspond à la notion géométrique usuelle de treillis , et la structure algébrique des treillis ainsi que la géométrie de l'ensemble des treillis sont relativement bien comprises. Les résultats importants obtenus par Borel , Harish-Chandra , Mostow , Tamagawa , M.S. Raghunathan , Margulis et Zimmer entre les années 1950 et 1970 ont fourni des exemples et ont généralisé une grande partie de la théorie aux groupes de Lie nilpotents et aux groupes algébriques semi-simples sur un corps local . Dans les années 1990, Bass et Lubotzky ont initié l'étude des treillis arborescents , qui demeure un domaine de recherche actif.

Les sujets abordés dans ce domaine comprennent :

Géométrie numérique

discrets (généralement des ensembles de points discrets ) considérés comme des modèles ou des images numérisés d'objets de l' espace euclidien 2D ou 3D .

En termes simples, la numérisation consiste à remplacer un objet par un ensemble discret de ses points. Les images que nous voyons sur l'écran de télévision, l' affichage matriciel d'un ordinateur ou dans les journaux sont en réalité des images numériques .

Ses principaux domaines d'application sont l'infographie et l'analyse d'images .

Géométrie différentielle discrète

géométrie différentielle . Au lieu de courbes et de surfaces lisses, on trouve des polygones , des maillages et des complexes simpliciaux . Elle est utilisée en infographie et en combinatoire topologique .

Les sujets abordés dans ce domaine comprennent :