Ceci est une version archivée de cette page, en date du 29 décembre 2020 à 10:29 et modifiée en dernier par CodexBot(discuter | contributions). Elle peut contenir des erreurs, des inexactitudes ou des contenus vandalisés non présents dans la version actuelle.
En géométrie, la somme de Minkowski est une opération sur les parties d'un espace vectoriel. À deux parties A et B elle associe leur ensemble somme, formé des sommes d'un élément de A et d'un élément de B :
.
La somme de deux compacts est compacte. Il est ainsi possible de restreindre l'opération à cet ensemble, qui peut être muni d'une distance, dite de Hausdorff. La somme de Minkowski est alors une opération continue. De plus elle respecte les convexes, c'est-à-dire que la somme de deux convexes est encore convexe. La mesure de la somme de deux convexes vérifie une majoration, dite inégalité de Brunn-Minkowski.
La somme de Minkowski intervient dans de nombreux domaines des mathématiques pures ou appliquées. Cet outil est à la base de nombreuses démonstrations de théorèmes isopérimétriques, visant à déterminer la partie de l'espace de plus vaste volume possible, la contrainte étant la donnée de la mesure de sa frontière. En géométrie euclidienne, on trouve les sphères de dimension n. La somme de Minkowski intervient aussi pour le comptage du nombre de face d'un polyèdre, résoudre des questions de pavages ou encore pour étudier la géométrie des convexes. Ils sont appliqués par exemple en cristallographie pour des raisons de pavages d'espace, en économie pour optimiser les productions possibles d'un groupe d'entreprises, ou encore pour étudier les mélanges.
Préambule
Exemples
L'ensemble de A à gauche est un triangle dont les coordonnées des sommets sont (0,-1), (0,1) et (1,0). À droite est illustré un triangle semblable B, orienté différemment. Les coordonnées sont (0,0), (1,-1) et (1,1). Si les ensembles A et B sont deux triplets, on trouve :
Si A et B sont les triangles illustrés en rouge, on trouve un hexagone, illustré par la figure en bas à droite.
De manière générale, la somme de deux polygones est encore un polygone. Cette propriété est vraie pour un polyèdre de dimension quelconque.
On peut remarquer l'analogie entre la somme de Minkowski et le produit de convolution. De manière imagée, on peut obtenir la surface de la somme A + B de deux ensembles en couvrant B de peinture et en faisant parcourir à son centre la surface A. Pour cette raison, cette somme de Minkowski est parfois appelée convolution de A et de B.
De manière évidente, la somme d'un ensemble A et d'un singleton {b} correspond à la translation de A par le vecteur b.
Il n'est guère plus complexe de se rendre compte que la somme de deux carrés est encore un carré. D'une manière plus générale, si C est un convexe, symétrique par rapport à l'origine, la somme C + C est égal au convexe 2C, ici 2C désigne l'homothétie de rapport 2. La démonstration est un peu plus subtile, elle est analogue au lemme préliminaire utilisé dans la démonstration du théorème de Minkowski. Pour s'en rendre compte, on peut remarquer que tout élément de 2C est élément de C + C, réciproquement soit u + v un élément de C + C, il s'écrit aussi comme le double de 1/2(u + v), or cet élément est dans C.
On peut citer un dernier exemple, que l'on trouve dans l'article théorème isopérimétrique. Soient C un compact convexe d'un plan euclidien et P un polygone convexe dont les sommets sont tous sur la frontière de C et dont la plus grande arête est d'une longueur majorée par ε. Alors la somme de P et du disque de centre le vecteur nul et de rayon ε contient le compact convexe C. Cette propriété est une étape pour établir qu'il n'existe aucune surface d'aire plus grande que le disque de même périmètre.
la somme, restreinte aux ensembles non vides fermés et bornés est une opération semi-continue supérieurement (cf Distance de Hausdorff).
Remarque : La somme de deux parties fermées n'est pas nécessairement fermée : par exemple en prenant dans le plan la droite des abscisses et l'hyperbole xy = 1, leur somme forme le plan privé d'une droite. Cependant, la somme d'un fermé et d'un compact est fermée.
La formule de Steiner a été découverte pour démontrer le théorème isopérimétrique. En dimension 2, il stipule que si C est une surface de périmètre p, alors son aire est plus petite que celle du disque de périmètre p. Si le périmètre p n'est pas fini, comme pour un compact construit à l'aide d'une courbe de Koch, la formule reste exacte, mais ne possède plus aucun intérêt. Le théorème prend la forme suivante :
,
l'égalité n'étant obtenue que dans le cas où le compact C est un disque.
Pour le démontrer, une approche consiste à étudier l'aire de la somme de Minkowski d'un convexe compact C et de tB, où t désigne un réel positif et B le disque unité. On trouve l'égalité suivante, si μ est la fonction volume qui à C associe son aire, et C est un ensemble convexe :
.
La fonction volume μ est définie de manière très générale, elle correspond à la mesure de Lebesgue, qui à un carré de côté 1 associe 1. Le périmètre d'une courbe est définie à la manière de Jordan, c'est-à-dire qu'il est égal à la borne supérieure des longueurs de lignes polygonales approximant la frontière. Sous cette forme, démontrer le théorème isopérimétrique revient à montrer que le polynôme du second degré, qui à t associe μ(C + t.B), possède un discriminant positif, ou encore que le polynôme admet une racine réelle.
Cette formule permet aussi d'obtenir une expression du périmètre p — toujours si C est convexe — en fonction de φ :
.
Dimension quelconque
Il est tentant de généraliser la formule, dans un espace euclidien E de dimension n. On peut considérer la mesure du volume sC1 + tC2, où C1 et C2 sont deux compacts convexes et s et t deux réels positifs. On obtient une expression polynomiale du type :
.
Les coefficients Vk s'appellent volumes mixtes de C1 et C2[1].
On dispose de quelques égalités évidentes :
.
Une autre est un peu plus délicate à démontrer dans le cas où C2 est égal à B :
.
Ici, n–1 désigne le volume (n – 1)-dimensionnel. Définir une mesure (n – 1)-dimensionnelle devient subtil. Une première méthode consiste à généraliser la technique utilisée en dimension 1, pour un arc rectifiable. Elle demande d'être adaptée et est spécifique aux convexes. La mesure de la surface est alors la borne supérieure des convexes polyédriques inclus dans C1. La convexité est indispensable, sinon le contre-exemple de droite montre que la définition n'a pas de sens. La surface que l'on souhaite mesurer est un cylindre, le polyèdre utilisé est un lampion dont les sommets sont situés sur des hexagones chaque fois décalés d'un douzième de tour. Si les plans des hexagones se rapprochent de plus en plus, la surface du polyèdre augmente jusqu'à l'infini[2]. Une autre technique consiste à utiliser une forme différentielle et plus précisément une forme volume. La difficulté réside alors dans le fait que la surface d'un convexe n'a pas de raison d'être une variété de classe C1. Il devient nécessaire d'utiliser des espaces comparables à ceux de Sobolev pour définir la surface[3].
Les volumes mixtes vérifient une majoration utilisée pour démontrer le théorème isopérimétrique pour les dimensions supérieures à 2. Elle porte le nom d'inégalité d'Alexandrov-Fenchel[4] :
.
Démonstrations
Ici, E désigne un espace euclidien de dimension n.
Si P est un polyèdre compact et convexe de E, la fonction qui à (s, t) associe la mesure μ(s.P + t.B) est un polynôme homogène de degré n :
Notons M cette mesure. M est la somme de la mesure μ(s.P) et de la croute ajoutée par la somme de t.B. Le terme associé à la mesure de μ(s.P) est une constante que multiplie sn.
Sur chaque face, on trouve un hypercubeHi1 de dimension n, de base la face en question et de hauteur t de dimension n - 1 et de mesure le produit d'une constante et de sn-1. Chacune de ces faces contribue au volume μ(P + t.B) sous la forme d'une expression linéaire en sn-1.t.
Entre ces hypercubes, on trouve des interstices Hj2, ayant la forme d'un prisme, d'arête l'intersection de deux faces, et de dimension n - 2, dont la mesure est le produit d'une constante avec sn-2 et de côtés deux faces d'hypercubes Hi1 ayant une arête de longueur t, le sommet un composé du produit d'un disque de rayon t et d'un hypercube isomorphe à l'arête. Ces prismes sont donc des portions de cylindre d'axe un hypercube de dimension n - 2 et de rayon r. Chacune de ces portions de cylindre contribue au volume μ(P + t.B) sous la forme d'une expression en sn-2.t2.
Les arêtes de dimension n - 2 ont comme extrémités des hypercubes de dimension n - 3 qui laissent place à des interstices, laissée vacant par les solides Hi1 et Hj2. Ces interstices Hk3, sont remplis par des primes, d'arêtes les intersections des arêtes précédentes, sont de dimension n - 3 et de mesure le produit d'une constante et de sn-3. Ces primes correspondent à des portions de produit de boule de dimension 3 et d'hypercubes arêtes de dimension n - 3. Leur somme correspond à une expression en sn-3.t3.
On continue ainsi jusqu'à la dimension 1, l'intersection des arêtes est alors de dimension 0 et correspond à un point. L'interstice correspond à une portion de boule, dont l'expression est le produit d'une constante par tn.
Le terme en sn correspond à la mesure de P, celui en sn-1.t à la mesure de la surface de P. Si s est égal à 0, on remarque que le volume est celui d'une boule de rayon t, la constante est celle associée au volume n dimensionnel d'une sphère.
Si C est un compact, convexe non vide de E, la fonction qui à (s, t) associe la mesure μ(s.C + t.B) est un polynôme homogène de degré n :
Soit (Cp) une suite décroissante de polyèdres convexes dont la limite, au sens de Hausdorff, est égale à C. Le paragraphe ensemble dense de l'article Distance de Hausdorff montre qu'une telle suite existe. Soit Pp(s, t) le polynôme homogène de degré n qui à (s, t) associe μ(s.Cp + t.B), l'objectif est de montrer que la suite (Pp) converge simplement.
La suite (s.Cp + t.B) est une suite de compacts, décroissante pour l'inclusion, elle est nécessairement convergente au sens de Hausdorff, montrons que la limite est égale à s.C + t.B. Tout ensemble de la suite contient s.C + t.B, la limite contient donc cet ensemble. Réciproquement si y n'est pas élément de s.C + t.B, il existe un nombre réel strictement positif ε tel que la boule de centre y et de rayon ε ait une intersection nulle avec s.C + t.B car cet ensemble est fermé. On en déduit que tout élément de s.Cn est à une distance supérieure à t + ε de y. Si s n'est pas nul, cela signifie aussi que y est à une distance supérieure à (t + ε)/s de C. À partir d'un certain N, pour toute valeur de p plus grande que N, Cp est à une distance de y strictement supérieure à t/s, et s.Cp + t.B ne peut contenir y. Si s est nul, la suite s.Cp + t.B est constante égale à t.B et est trivialement convergente.
Comme la suite (s.Cp + t.B) est une suite de compacts strictement décroissante, de limite s.C + t.B, et que la fonction μ est semi-continue supérieurement, la suite μ(s.Cp + t.B) est convergente (cf le paragraphe Fonctions continues de l'article Distance de Hausdorff). Ce qui signifie exactement que la suite (Pp) converge simplement.
Chaque polynôme de la suite (Pp) est un polynôme homogène de degré n, cette suite fait partie de l'espace vectoriel des polynômes à deux variables de degré inférieur à n et est de dimension finie. Sur cet espace, la topologie de la convergence simple est compatible avec l'addition et la multiplication externe, ce qui signifie que ces deux opérations sont continues. Or, sur un espace vectoriel réel de dimension finie, il n'existe qu'une topologie compatible avec ses deux opérations, (cf topologie d'un espace vectoriel de dimension finie). Cette topologie est induite par n'importe quelle norme, par exemple celle de la convergence uniforme sur le disque de rayon r, où r désigne un nombre réel strictement positif. L'espace vectoriel des polynômes à deux variables homogènes et de degré n est complet pour cette norme, ce qui montre que la suite (Pp) converge vers un polynôme P homogène de degré n.
Cette limite P est, par construction, la fonction qui à (s, t) associe μ(s.C + t.B), ce qui démontre la proposition.
Inégalité de Brunn-Minkowski
Démontrée par Hermann Brunn[5] et Hermann Minkowski[6] dans le cas où les deux compacts sont convexes puis dans le cas général par Lazar LyusternikLazar Lyusternik[7],[8], l'inégalité de Brunn-Minkowski est une minoration du volume de la somme de deux parties compactes d'un espace euclidien :
Soient E un espace euclidien de dimension n, μ la mesure de Lebesgue sur E et A et B deux compacts non vides de E. L'inégalité suivante est vérifiée[9],[10] :
.
Démonstration
L'espace E est équipé d'une base orthonormée, puis il est quadrillé par une grille composée d'hyperplans dont les directions sont orthogonales à un des vecteurs de la base. Ces hyperplans sont régulièrement espacés, avec un pas de 1/2p, ou p est un entier strictement positif. Cette grille pave l'espace à l'aide de petits hypercubes d'arêtes de longueur 1/2p. La mesure de Lebesgue choisie est celle qui associe à un hypercube de côté de longueur 1 la valeur 1.
Ces hypercubes permettent d'approximer un compact. Par exemple, sur la figure de droite un pentagone régulier est approximé par des carrés bleus. Affiner la grille revient à choisir une valeur plus élevée pour p. La figure de droite illustre aussi une deuxième approximation par des petits carrés rouges obtenu pour un incrément de 1 de la valeur p. L'article Distance de Hausdorff montre que cette technique permet de construire une suite (An) de compacts contenant A et approximant de plus en plus précisément A, au sens de la distance de Hausdorff.
La démonstration proposée ici[11] se déroule en trois temps. Dans un premier temps, on la démontre dans le cas où A est un hypercube de la grille et B un hypercube inclus dans un de ceux de la grille et dont les arêtes sont toutes de longueur a = 1/2p sauf celles parallèles au premier vecteur de la base qui sont de longueur λ.a. Ici, λ désigne un nombre réel strictement positif et plus petit que 1.
Dans le cas où A et B sont deux hypercubes décrits ci-dessus, la majoration de Brunn-Minkowski est vérifiée :
Le cas est suffisamment simple pour permettre un calcul effectif des trois mesures.
Démontrer la majoration dans le cas présent revient à montrer que la fonction f de dans R, où R désigne l'ensemble des nombres réels, est strictement positif, sur et nulle en 1.
Il est clair que la fonction f est nulle au point 1, il suffit de montrer qu'elle est strictement décroissante pour conclure. La fonction f est dérivable sur , il suffit de montrer que sa dérivée est strictement négative, ce qui se vérifie aisément.
On suppose maintenant que A et B sont deux unions finies d'intérieurs d'hypercubes de la grille ou de partie d'hypercubes ouverts dont une des coordonnées est comprise entre 1/2p.(δ + λ) et 1/2p.(δ + 1). C'est-à-dire que les hypercubes sont du type de la proposition précédente. Les valeurs q et r désignent le nombre d'hypercubes composant respectivement A et B.
Dans le cas où A et B sont deux compacts de la forme décrite ci-dessus, la majoration de Brunn-Minkowski est vérifiée :
On raisonne par récurrence sur l'entier s égal à la somme de q et de r. Si s est égal à 2, le résultat est une conséquence directe de la proposition précédente.
On suppose le résultat établi jusqu'à une valeur s0 et on suppose que la somme de q et de r est égale à s0 + 1. On sépare l'espace euclidien E en deux connexes par un des hyperplansHA orthogonal à l'un des vecteurs de la base orthonormale qui définit la grille. Il existe un hyperplan de cette nature qui décompose A en deux ouverts disjoints A1 et A2 tel que A2 comporte au moins un hypercube et tel que A1 ne soit pas l'ensemble vide. A1 et A2 sont alors composés d'au plus de q - 1 hypercubes. On note θ le nombre réel strictement positif suivant :
On sépare B en deux ensembles B1 et B2 par un hyperplan HB parallèle au précédent, de telle manière à ce que :
Ni B1 et B2 ne contiennent de vecteurs de l'hyperplan HB, en conséquence, B contient mais n'est pas nécessairement égal à l'union de B1 et B2, mais comme un sous ensemble inclus dans un hyperplan est de mesure nulle, l'égalité précédente est vérifiée. Cette fois ci, rien ne prouve que B1 et B2 contiennent moins d'hypercubes que B, mais il est certain qu'ils n'en contiennent pas plus. Les propriétés de la somme de Minkowski montrent que :
Considérons le vecteur de la base orthonormale orthogonale aux deux hyperplans HA et HB, les coordonnées sur ce vecteur de tout élément de A1 + B1 sont strictement plus petites que celles des vecteurs de A2 + B2, ce qui montre que les deux ensembles sont disjoints et :
Comme A1 et A2 contiennent strictement moins que q petits hypercubes et que B1 et B2 n'en contiennent pas plus que r, il est possible d'appliquer l'hypothèse de récurrence :
Ce que l'on peut encore écrire :
Ce qui montre la majoration qui termine la démonstration :
Il est maintenant possible de prouver la majoration de Brunn-Minkowski dans le cas général. On utilise pour cela un passage à la limite utilisant la distance de Hausdorff. Soit ε un réel strictement positif et A et B deux compacts de E. L'objectif de la démonstration est de montrer que la somme de la mesure de A + B et de ε majore bien le deuxième membre de l'inégalité. On utilise trois propriétés démontrées dans l'article Distance de Hausdorff.
Si A et B sont deux compacts non vides, l'inégalité de Brunn-Minkowski est vérifiée :
Dans un premier temps, on utilise la semi-continuité supérieure de la fonction mesure pour la distance de Hausdorff. Si EH désigne l'ensemble des compacts non vides de E et d la distance de Hausdorff :
Il s'agit maintenant de construire le bon ensemble C. On utilise l'existence de deux ensembles Aε et Bε compacts contenant strictement A et B et tel que :
Les deux ensembles Aε et Bε sont des unions finies d'hypercubes fermés de la grille, pour une valeur de p suffisamment élevée. L'existence de tels ensembles provient du fait que les unions finies d'hypercubes fermés pris dans la grille forment un ensemble dense si p décrit les entiers positifs. La démonstration de la continuité de la somme de Minkowski pour la distance de Hausdorff (cf l'article Distance de Hausdorff) montre que :
On choisit C égal à la somme de Aε et Bε, ce qui montre que :
On retire à l'ensemble Aε + Bε son intersection avec les hyperplans de la grille, ce qui ne modifie pas sa mesure. On se trouve alors dans les hypothèses de la proposition précédente et :
Ici, Aoε et Boε désignent les ensembles Aε et Bε ôtés de leurs intersections avec les hyperplans de la grille. Rajouter cette intersection ne modifie en rien les mesures, ce qui montre que :
Par hypothèse, les ensembles Aε et Bε contiennent A et B. Leur mesure est plus grande, et :
Cette majoration est vraie pour toute valeur de ε strictement positive, ce qui montre le résultat cherché[12].
Si les deux compacts A et B sont convexes et homothétiques, il y a égalité.
↑Cet exemple est tiré de Marcel Berger et Bernard Gostiaux, Géométrie différentielle : variétés, courbes et surfaces [détail des éditions] p. 226.
↑Pour plus de détails, voir : (en) Herbert Federer, Geometric Measure Theory, Springer-Verlag, 1969 (ISBN978-3-540-60656-7), 3.2.37, 3.2.39, 3.2.26.
↑(en) A. D. Alexandrov, Selected Works, CRC, 2002 (ISBN2881249841).
↑(de) H. Brunn, Über Ovale und Eiflächen, Munich, (thèse).
↑(de) Hermann Minkowski, Geometrie der Zahlen, Leipzig, Teubner, .
↑(de) Lazar A. Lyusternik, « Die Brunn–Minkowskische Ungleichnung für beliebige messbare Mengen », C.R. Acad. Sci. URSS, vol. 8, , p. 55-58.
↑Bernard Maurey, « Inégalité de Brunn-Minkowski-Lusternik, et autres inégalités géométriques et fonctionnelles », Séminaire Bourbaki, t. 46, 2003-2004, p. 95-114 (lire en ligne).