Théorème de Carathéodory (géométrie)

Par exemple le point (1/4, 1/4) de l'enveloppe convexe des points (0, 0), (1, 0), (1, 1), (0, 1) se trouve dans l'intérieur du triangle (0, 0), (1, 0), (0, 1).

Le théorème de Carathéodory est un théorème de géométrie relatif aux enveloppes convexes dans le contexte des espaces affines de dimension finie. Dans le plan, il affirme que tout point dans l'enveloppe convexe d'un ensemble de points $A$ est dans l'intérieur d'un triangle dont les sommets sont dans $A$ (l'enveloppe convexe d'un ensemble de points $A$ est l'ensemble des barycentres de trois points de $A$).

Énoncé

Le théorème, établi par le mathématicien grec Constantin Carathéodory, affirme que :

Théorème — Dans un espace affine de dimension $n$, l'enveloppe convexe d'un sous-ensemble $A$ est l'ensemble des barycentres à coefficients positifs ou nuls de familles de $n+1$ points de $A$.

Preuves

La preuve usuelle

Notons $\mathrm {Conv} (A)$ l'enveloppe convexe de $A$, et $\Gamma$ l'ensemble des barycentres à coefficients positifs ou nuls d'au plus $n+1$ points de $A$. On veut montrer l'égalité de ces deux ensembles.

L'inclusion $\Gamma \subseteq \mathrm {Conv} (A)$ est évidente. Pour montrer $\mathrm {Conv} (A)\subseteq \Gamma$, la démarche de la preuve est de montrer que pour tout $p\geq n+1$, si un élément $x$ de l'enveloppe convexe s'écrit comme combinaison convexe de $p+1$ points (c'est-à-dire comme barycentre à coefficients positifs ou nuls de ces points), alors c'est une combinaison convexe de $p$ points bien choisis parmi ces $p+1$ ; on réitère alors le procédé jusqu'à obtenir $x\in \Gamma$.

Soit $x\in \mathrm {Conv} (A)$. Ainsi $x$ s'écrit $x=\sum _{i=1}^{p+1}\lambda _{i}a_{i}$, où $p\geq 1$ est un entier, les $\lambda _{i}$ sont des réels positifs ou nuls de somme 1, et les $a_{i}$ sont des points de $A$.

Si $p\leq n$, alors $x\in \Gamma$. Si $p\geq n+1$, alors $(a_{1},\dots ,a_{p+1})$ est affinement lié, c'est-à-dire que l'un des points, disons par exemple $a_{1}\,$, est barycentre des autres : il existe des réels $t_{2},\cdots ,t_{p+1}$ de somme 1 tels que $a_{1}=\sum _{i=2}^{p+1}t_{i}a_{i}$.

En posant $\mu _{1}=1\,$ et pour $i>1\,$, $\mu _{i}=-t_{i}\,$, on obtient : $\mu _{1}>0\,$, $\sum _{i=1}^{p+1}\mu _{i}=0$ et $\sum _{i=1}^{p+1}\mu _{i}a_{i}={\overrightarrow {0}}$.

Choisissons $k$ tel que : ${\frac {\lambda _{k}}{\mu _{k}}}=\inf\{{\frac {\lambda _{i}}{\mu _{i}}},1\leq i\leq p+1,\mu _{i}>0\}$ et remplaçons, dans l'expression de $x$, le point $a_{k}$ par $\sum _{i\neq k}{\frac {-\mu _{i}}{\mu _{k}}}a_{i}$.

Par "associativité du barycentre" on obtient $x=\sum _{i\neq k}\delta _{i}a_{i}$, où les $\delta _{i}\,$, définis par $\delta _{i}=\lambda _{i}-\lambda _{k}{\frac {\mu _{i}}{\mu _{k}}}$, sont des réels de somme 1, dont il reste à montrer qu'ils sont tous positifs ou nuls.

Si $\mu _{i}>0\,$, alors ${\frac {\lambda _{i}}{\mu _{i}}}\geq {\frac {\lambda _{k}}{\mu _{k}}}$ et donc $\delta _{i}\geq 0$. Si $\mu _{i}\leq 0$, alors $\delta _{i}\,$ est positif en tant que somme de deux termes positifs.

$x$ est donc barycentre à coefficients positifs ou nuls de $p$ éléments de $A$.

Une preuve comme conséquence du théorème de Helly

Les possibilités de déduire l'un de l'autre les théorèmes de Helly et de Caratheodory, le premier parlant d'intersections finies de convexes, qu'on peut ramener au seul problème d'intersections finies de demi-espaces, tandis que le second parle d'enveloppe convexe d'un nombre fini de points sont fort instructives pour illustrer les techniques de dualité en géométrie convexe, qui échangent points et demi-espaces. Deux preuves du théorème de Helly dans l'article qui lui est consacré en font une conséquence de Carathéodory, dont une fort instructive via le lemme de Farkas ; aller dans l'autre sens (tirer Carathéodory de Helly) est plus facile encore, et on peut se borner à utiliser un théorème de Gordan d'esprit voisin du lemme de Farkas, mais de démonstration nettement plus aisée.

Soit $x$ un point de l'enveloppe convexe de $A$. Quitte à translater la figure, on peut supposer que $x=0$. Il existe donc une famille finie de points de $A$, soit $(a_{1},\ldots ,a_{k})$ dont $0$ est un barycentre à coefficients positifs ou nuls. Si $k\leq n+1$ il n'y a rien à faire, supposons donc $n+2\leq k$. On munit $E$ d'une structure euclidienne, et pour chacun des $a_{j}$ on considère la forme linéaire $f_{j}$ définie sur $E$ par $f_{j}(y)=<a_{j}|y>$ et le demi-espace $R_{j}=\{y\in E|f_{j}(y)>0\}$.

Le théorème de Gordan (en réalité le sens évident de celui-ci) assure que les demi-espaces $R_{j}$ ($j$ variant entre $1$ et $k$) ont une intersection vide. Le théorème de Helly assure à son tour qu'il en existe une sous-famille avec seulement $d+1$ membres qui a à son tour une intersection vide. Le sens plus significatif du théorème de Gordan permet alors de conclure que les $d+1$ points $a_{j}$ correspondant à cette liste ont à leur tour $0$ dans leur enveloppe convexe.

Corollaire : un résultat de compacité

Corollaire — Dans un espace affine de dimension finie, l'enveloppe convexe d'un compact est compacte.

Soit A le compact et $\Delta \,$ l'ensemble des (p+1)-uples de nombres positifs de somme 1. Alors $\mathrm {Conv} (A)$ est l'image du compact $A^{p+1}\times \Delta$ par l'application continue

$(a_{1},\cdots ,a_{p+1},u_{1},\cdots ,u_{p+1})\mapsto \sum _{i=1}^{p+1}u_{i}a_{i}.$

Un théorème de Fenchel et Bunt

Si l'on suppose en outre que A est connexe (ou même seulement qu'il n'a pas trop de morceaux), on peut limiter le nombre de sommets des simplexes nécessaires pour construire l'enveloppe convexe à la dimension de l'espace ambiant. L'énoncé précis, dû à W. Fenchel et L. Bunt est le suivant :

Théorème — Dans un espace affine de dimension $n$, soit $A$ un sous-ensemble ayant au plus $n$ composantes connexes. Alors l'enveloppe convexe de $A$ est l'ensemble des barycentres à coefficients positifs ou nuls de familles de $n$ points de $A$.

Ainsi dans le cas le plus simple, celui de la dimension $2$, si une figure plane $A$ est formée d'au plus deux morceaux, on peut reconstituer son enveloppe convexe en faisant la réunion de tous les segments ayant leurs deux extrémités dans $A$.

Démonstration

Préparons d'abord le terrain pour la preuve en envisageant la situation suivante : soit $(y_{1},\ldots ,y_{n+1})$ un $n+1$-uplet de $\mathbb {R} ^{n}$ ayant pour enveloppe affine $\mathbb {R} ^{n}$ tout entier, et positionné de telle sorte que $y_{1}+\cdots +y_{n+1}=0$. Pour chaque indice $i$ entre $1$ et $n+1$, notons $C_{i}$ l'ensemble des points $x$ de $\mathbb {R} ^{n}$ qui peuvent s'écrire $x=\alpha _{1}y_{1}+\cdots +\alpha _{i-1}y_{i-1}+\alpha _{i+1}y_{i+1}+\cdots +\alpha _{n+1}y_{n+1}$ avec des coordonnées $\alpha _{k}$ toutes strictement positives (et pas de terme en $y_{i}$).

On vérifie alors aisément les informations suivantes :

• (i) Chaque $C_{i}$ est un ouvert de $\mathbb {R} ^{n}$
• (ii) Tout point de $\mathbb {R} ^{n}$ peut s'écrire de façon unique comme une combinaison linéaire $x=\alpha _{1}y_{1}+\cdots +\alpha _{n+1}y_{n+1}$ à coefficients positifs ou nuls, l'un au moins des coefficients étant nul
• (iii) Pour $i\not =j$, $C_{i}$ et $C_{j}$ sont disjoints.

(Pour la première, on songera que $(y_{1},\ldots ,y_{i-1},y_{i+1},\ldots ,y_{n+1})$ est une base de $\mathbb {R} ^{n}$ et qu'on peut donc écrire tout point proche d'un $\alpha _{1}y_{1}+\cdots +\alpha _{i-1}y_{i-1}+\alpha _{i+1}y_{i+1}+\cdots +\alpha _{n+1}y_{n+1}$ de $C_{i}$ par une formule ayant la même forme dans laquelle les coefficients sont proches des $\alpha _{i}$ ; pour la seconde, on s'assurera d'abord qu'étant donnée une écriture $x=\alpha _{1}y_{1}+\cdots +\alpha _{n+1}y_{n+1}$ d'un point de $R^{n}$ comme combinaison linéaire des $y_{i}$, ses autres écritures comme telles combinaisons linéaires sont exactement les écritures $x=(\alpha _{1}+\rho )y_{1}+\cdots +(\alpha _{n+1}+\rho )y_{n+1}$ où $\rho$ parcourt $\mathbb {R}$, une fois ceci connu, l'ajustement requis des coefficients est atteint pour le seul choix de $\rho =-\mathrm {Min} _{i}(\alpha _{i})$ ; la troisième découle immédiatement de la seconde, puisqu'un hypothétique point de $C_{i}\cap C_{j}$ aurait deux écritures différentes vérifiant toutes les conditions ci-dessus).

On peut alors entamer la démonstration proprement dite. Soit un point arbitraire de $\mathrm {Conv} (A)$, l'objectif étant de parvenir à l'écrire comme barycentre à coefficients positifs de $n$ points de $A$ ; quitte à prendre un système de coordonnées approprié sur l'espace affine ambiant, on peut supposer que celui-ci est $\mathbb {R} ^{n}$ et que le point étudié est l'origine. Le théorème de Carathéodory nous fournit déjà une écriture :

$(1)\qquad 0=\lambda _{i}x_{1}+\cdots +\lambda _{n+1}x_{n+1}$

de $0$ comme combinaison linéaire à coefficients positifs de $n+1$ points de $A$.

Deux cas dégénérés se traitent sans difficulté : si un au moins des $\lambda _{i}$ est nul, on a terminé ; si l'enveloppe affine des $x_{i}$ n'est pas $\mathbb {R} ^{n}$ tout entier, en appliquant le théorème de Carathéodory dans cette enveloppe affine on peut diminuer d'au moins un le nombre de ceux-ci dans l'écriture de $0$.

Reste le cas sérieux, celui où les $x_{i}$ forment un repère affine de $\mathbb {R} ^{n}$, tous les coefficients $\lambda _{i}$ qui apparaissent dans $(1)$ étant strictement positifs. On pose alors pour chaque indice $i$, $y_{i}=-\lambda _{i}x_{i}$ : ces points sont positionnés comme sommets d'un simplexe dont le centre de gravité est à l'origine et on peut donc utiliser les $C_{i}$ introduits en préliminaires.

Parmi les $n+1$ points $x_{i}$ de $A$, qui a au plus $n$ composantes connexes, il est inévitable que deux au moins, disons $x_{j}$ et $x_{k}$ appartiennent à une même composante connexe $A_{0}$ de $A$. Cela entraîne que $A$ ne peut être inclus dans $C_{1}\cup \cdots \cup C_{n+1}$ : si tel était le cas, la division de $A_{0}$ en les deux parties $A_{0}\cap C_{j}$ et $A_{0}\cap \left(C_{1}\cup \cdots C_{j-1}\cup C_{j+1}\cup \cdots \cup C_{n+1}\right)$ découperait $A_{0}$ en deux ouverts (dans $A_{0}$) disjoints, non vides puisque l'un contient $x_{j}$ et l'autre $x_{k}$. On a donc ainsi montré que $A$ contient au moins un point $x$ qui n'est dans aucun des $C_{i}$.

Vu d'une part la remarque (i), et vu d'autre part la non-appartenance de $x$ aux $C_{i}$, c'est donc que $x$ peut être écrit comme combinaison linéaire des $y_{i}$ à coefficients tous positifs dont deux au moins sont nuls ; quitte à renuméroter les $x_{i}$, on supposera pour simplifier l'écriture que ce sont les deux premiers.

On dispose alors, pour ce point $x$ de $A$ d'une écriture :

$x=\beta _{3}y_{3}+\cdots +\beta _{n+1}y_{n+1}$

dans laquelle tous les $\beta _{i}$ sont positifs.

Il ne reste plus qu'à regrouper différemment celle-ci, en allant rechercher la définition des $y_{i}$ :

$0={x+\lambda _{3}\beta _{3}x_{3}+\cdots +\lambda _{n+1}\beta _{n+1}x_{n+1} \over {1+\lambda _{3}\beta _{3}+\cdots +\lambda _{n+1}\beta _{n+1}}}$

pour obtenir ce qu'on cherchait depuis le début : une écriture de $0$ comme barycentre à coefficients positifs de seulement $n$ points de $A$.