Théorème de helly

Théorème de helly

Théorème de Helly

Le théorème de Helly est un résultat combinatoire sur les convexes.

Ce résultat a été prouvé en 1913 par Eduard Helly, et il a été publié par Johann Radon en 1921[1],[2].

Énoncé

Théorème — On considère X_1,X_2,\dots,X_n une famille finie de n ensembles convexes de Rd (où on suppose que n\geq d+1). On suppose que, pour tout choix de d + 1 convexes parmi X_1,X_2,\dots,X_n, ces d + 1 convexes se rencontrent. Il existe alors un point qui appartient à tous les Xi.

Il est facile d'étendre le théorème à des familles infinies d'ensembles convexes, en rajoutant une hypothèse de compacité

Corollaire — Si (X_i)_{i \in I} est une collection de sous-ensembles compacts convexes de Rd et que pour toute partie J \subset I finie de cardinal inférieur ou égal à d + 1, \bigcap_{j \in J} X_j \ne\varnothing alors l'intersection de tous les Xi est non vide, c'est-à-dire : \bigcap_{i \in I} X_i \ne\varnothing.

Preuves

On donne la preuve dans le cas fini (le cas infini se ramène au cas fini par un argument de compacité).

Il y a plusieurs preuves du théorème de Helly[3], mais toutes se prêtent bien à être aiguillées par l'énoncé intermédiaire suivant :

Énoncé intermédiaire — Dans un espace affine de dimension d, soit A=(a_1,\ldots,a_{d+2} ) un d + 2-uplet de points. Pour chaque indice i variant entre 1 et d + 2, on note \Delta_i=\mathrm{Conv}\left(a_1, \dots, a_{i-1}, a_{i+1}, \ldots, a_{d+2}\right) l'enveloppe convexe des points de A autres que le point ai.

Il existe alors un point commun aux d + 2 simplexes Δi.

Dans tous les modes de démonstration, il y a un travail géométrique un peu subtil à faire pour parvenir à cet énoncé intermédiaire ; en revanche terminer la preuve ne demande pas d'idée bien compliquée.

Commençons donc par le plus facile, en montrant que l'énoncé intermédiaire entraîne le théorème de Helly sous la forme donnée plus haut.

Supposons d'abord que n = d + 2. Les hypothèses du théorème assurent l'existence d'un point a1 qui se trouve dans l'intersection des X_2,X_3,\dots,X_{d+2}.

a_1 \in \bigcap_{i=2}^{d+2} X_i

De la même manière on peut définir pour tout j\in\{1,2,\dots,{d+2}\} un élément aj dans l'intersection des X_i, i \neq j

a_j \in \bigcap_{i=1, i \neq j}^{d+2} X_i.

Appliquons l'énoncé intermédiaire à ces points : il fournit un point x qui est à la fois dans tous les simplexes Δi. Mais, par définition de Δi, tous les sommets de ce simplexe sont dans Xi. Donc x est un point de Xi pour tout i.

À présent, raisonnons par récurrence : supposons que n > d + 2 et que le résultat soit vrai au rang n − 1. Le raisonnement précédent montre que toute intersection de d + 2 ensembles convexes est non vide. On considère la nouvelle collection obtenue en remplaçant Xn − 1 et Xn par l'ensemble X_{n-1}\cap X_n.

Dans cette nouvelle collection, chaque intersection de d + 1 ensembles est non vide. L'hypothèse de récurrence implique donc que l'intersection de cette nouvelle collection est non vide ; mais cette intersection est la même que celle de la collection initiale.

On va maintenant donner plusieurs preuves de l'énoncé intermédiaire.

Première preuve : via le théorème de Radon

S'il y a une répétition dans la liste de points (a_1,\ldots,a_{d+2} ), disons aj = ak, avec j \neq k, alors aj est clairement dans l'intersection \bigcap_{i = 1}^{d+2} \Delta_i, et la propriété est prouvée. Sinon, on applique le théorème de Radon à l'ensemble A=\{a_1,a_2,\dots,a_{d+2}\}.

Ce théorème assure l'existence de deux sous-ensembles disjoints A_1,A_2\subset A tels que l'enveloppe convexe de A1 intersecte celle de A2. Il existe donc un point x appartenant à l'intersection des deux enveloppes convexes de A1 et A2. On va montrer que l'intersection des Δi contient ce point x, ce qui démontrera l'énoncé intermédiaire.

Prenons j\in\{1,2,\dots,{d+2}\}. Si a_j\in A_1, alors a_j\notin A_2, et par conséquent tous les points de A2 sont des ak avec k\not= j. Or de tels points sont dans Δj par définition, et donc A_2\subset \Delta_j. Comme Δj est convexe, il contient alors l'enveloppe convexe de A2 et par conséquent on a : x\in \Delta_j. De la même manière, si x_j\notin A_1, alors A_1\subset \Delta_j, et le même raisonnement donne x\in \Delta_j. Le point x fourni par Radon est donc bien commun à tous les Δi.

Deuxième preuve : via le théorème de Carathéodory

On munit l'espace affine d'une structure euclidienne.

Sur le polytope compact enveloppe convexe des points de A=(a_1,\ldots,a_{d+2} ), on considère la fonction continue f définie par :

f(x)=\mathrm{Max}_{1\leq i\leq d+2}\left(d(x,\Delta_i)\right)

puis on prend un point x de ce polytope en lequel elle admet son minimum. Montrer que les simplexes se rencontrent revient donc à montrer que f(x) = 0.

Le théorème de Carathéodory assure qu'on peut extraire de A une sous-famille avec seulement d + 1 points dont x est barycentre à coefficients positifs, autrement dit qu'il existe un indice i tel que x appartient à Δi. Quitte à renuméroter les points de A, on supposera que x appartient à Δ1.

Pour \theta\in[0,1], on va noter xθ = (1 − θ)x + θa1 le point courant du segment [x,a1].

L'idée de la fin de la preuve est alors la suivante : puisque a1 est dans \Delta_2\cap\cdots\cap\Delta_{d+2}, quand on fait glisser xθ le long du segment [x,a1] en direction de a1, ce point se rapproche de tous les simplexes \Delta_2,\ldots,\Delta_{d+2}. Par ailleurs, il s'éloigne peut-être de Δ1, mais au départ il en était à distance nulle et pour θ petit il en est encore à distance très petite et donc sans influence sur la valeur f(xθ) (puisque c'est un Max) —du moins si f(x)\not=0. Le résultat de ces observations, c'est que f(xθ) commence par diminuer quand θ augmente en restant suffisamment petit, et diminue même strictement si f(x)\not=0. Ceci contredit la minimalité de f(x).

Troisième preuve : par le théorème de Carathéodory et le lemme de Farkas

On va montrer le théorème par l'absurde. Supposons donc l'intersection des Δi vide.

Chacun des simplexes Δi est une intersection d'un nombre fini de demi-espaces. Énumérons la liste complète de ces demi-espaces R_1, R_2,\ldots,R_k de \R^d. On remarque tout de suite que l'intersection des Δi est égale à l'intersection des Rj qui est donc elle aussi vide.

Pour chacun de ces demi-espaces, prenons une forme affine fj pour laquelle R_j=\{x\in E\,\mid\, f_j(x)\geq 0\}.

Par le lemme de Farkas sous sa forme de critère de consistance pour un système d'inéquations affines, il existe donc une combinaison linéaire à coefficients positifs des fj égale à la forme constante − 1. Dit autrement, il existe un λ > 0 tel que − λ soit dans l'enveloppe convexe des fj.

Par le théorème de Carathéodory, il existe une sous-collection d'au plus d + 1 de ces fj qui contienne encore − λ dans son enveloppe convexe. En réappliquant le lemme de Farkas (dans ce sens c'est une évidence), l'intersection des Rj correspondants est alors vide.

Pour chacun d'entre eux, prenons un simplexe qu'il contient parmi la liste des Δi : ces simplexes sont au plus d + 1 donc se rencontrent par hypothèse. C'est contradictoire.

Notes et références

  1. Johann Radon, Mengen konvexer körper, die einen gemeinsamen Punkt enthalten, Math. Ann., 83:113-115, 1921
  2. Jiri Matousek, Lectures on Discrete Geometry, Graduate Texts in Mathematics, Springer, 2002
  3. Les deux premières données ci-dessous sont adaptées de l'ouvrage d'Eggleston référencé ci-dessous, p. 33-34 pour la première, qui est celle publiée par Radon, p. 39-40 pour la seconde. La troisième est de Terence Tao qui l'a publiée sur son blog le 30 novembre 2007 et est disponible en ligne.
  • H. G. Eggleston, Convexity, Cambridge Univ. Press
  • S. R. Lay, Convex Sets and Their Applications, Wiley.
  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Th%C3%A9or%C3%A8me de Helly ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Théorème de helly de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Théorème de Helly — dans le plan : si trois quelconques des convexes de la famille se rencontrent alors l intersection de tous ces convexes est non vide. Le théorème de Helly est un résultat combinatoire sur les convexes. Ce résultat a été prouvé en 1913 par… …   Wikipédia en Français

  • Théorème de carathéodory (géométrie) — 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. Sommaire 1 Énoncé 2 Preuves 2.1 La preuve usuelle …   Wikipédia en Français

  • Théorème de Radon (Géométrie) — Sommaire 1 Énoncé 2 Preuve 3 Théorème de Tverberg 4 Notes et références // …   Wikipédia en Français

  • Théorème de radon (géométrie) — Sommaire 1 Énoncé 2 Preuve 3 Théorème de Tverberg 4 Notes et références // …   Wikipédia en Français

  • Theoreme de Hahn-Banach — Théorème de Hahn Banach Ce théorème, auquel a été donné le nom des deux mathématiciens Hans Hahn et Stefan Banach, garantit l existence d une forme linéaire vérifiant certaines conditions (valeurs imposées sur une partie de l espace, mais… …   Wikipédia en Français

  • Théorème de hahn-banach — Ce théorème, auquel a été donné le nom des deux mathématiciens Hans Hahn et Stefan Banach, garantit l existence d une forme linéaire vérifiant certaines conditions (valeurs imposées sur une partie de l espace, mais limitées partout). En… …   Wikipédia en Français

  • Theoreme de projection sur un convexe ferme — Théorème de projection sur un convexe fermé En mathématiques, le théorème de projection orthogonale sur un convexe est un résultat de minimisation de la distance qui généralise la projection orthogonale sur un espace vectoriel. Il remplace… …   Wikipédia en Français

  • Théorème de projection orthogonale sur un convexe — Théorème de projection sur un convexe fermé En mathématiques, le théorème de projection orthogonale sur un convexe est un résultat de minimisation de la distance qui généralise la projection orthogonale sur un espace vectoriel. Il remplace… …   Wikipédia en Français

  • Theoreme de Minkowski — Théorème de Minkowski En mathématiques, le théorème de Minkowski est un résultat concernant la géométrie des réseaux. Il relie le nombre de points du réseau contenu dans une partie convexe symétrique au volume fondamental du réseau. Ce théorème… …   Wikipédia en Français

  • Théorème de minkowski — En mathématiques, le théorème de Minkowski est un résultat concernant la géométrie des réseaux. Il relie le nombre de points du réseau contenu dans une partie convexe symétrique au volume fondamental du réseau. Ce théorème est utilisé en théorie… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”