Enveloppe convexe

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Analogie avec un élastique entourant des points dans le plan, l'enveloppe convexe est la région délimitée par la ligne bleue.

L'enveloppe convexe d'un objet ou d'un regroupement d'objets géométriques est l'ensemble convexe le plus petit parmi ceux qui le contiennent.

Dans un plan, l'enveloppe convexe peut être comparée à la région limitée par un élastique qui englobe tous les points qu'on relâche jusqu'à ce qu'il se contracte au maximum. L'idée serait la même dans l'espace avec un ballon qui se dégonflerait jusqu'à être en contact avec tous les points qui sont à la surface de l'enveloppe convexe.

Définition et propriétés élémentaires[modifier | modifier le code]

On supposera être dans un contexte où la notion de sous-ensemble convexe a un sens (par exemple en géométrie affine sur les réels), et on notera E le cadre géométrique où on se place.

Définition — Soit A une partie de E. L'enveloppe convexe de A est l'intersection de toutes les parties convexes de E qui contiennent A.

Cette définition a un sens, puisqu'il existe au moins une partie convexe de E qui contient A, à savoir E lui-même.

De cette définition et du fait qu'une intersection quelconque d'ensembles convexes est un ensemble convexe, on déduit la caractérisation suivante de l'enveloppe convexe.

Proposition — L'enveloppe convexe de A est la plus petite partie convexe de E qui contient A.

Développé de façon plus détaillée, ce résultat caractérise l'enveloppe convexe Conv(A) comme l'unique sous-ensemble de E qui vérifie les trois conditions suivantes :

  • Conv(A) est convexe ;
  • A est inclus dans Conv(A) ;
  • si C est un sous-ensemble convexe de E contenant A, alors Conv(A) est inclus dans C.

Description en termes de barycentres[modifier | modifier le code]

Dans la suite de cette section, on supposera que E est un espace affine réel. On peut alors énoncer[1] :

Proposition — L'enveloppe convexe de A est l'ensemble des combinaisons convexes (c'est-à-dire des barycentres à coefficients positifs ou nuls) de familles de points de A.

Autrement dit : les éléments de l'enveloppe convexe de A sont exactement les points x de E qu'on peut écrire sous la forme :

x=\sum_{i=1}^p \lambda_i a_i, expression dans laquelle p est un entier, les ai sont dans A, les coefficients λi sont réels positifs et de somme \sum_{i=1}^p  \lambda_i=1.

Le cas de la dimension finie : un théorème de Carathéodory[modifier | modifier le code]

L'énoncé qui précède peut être amélioré en dimension finie, comme remarqué par Constantin Carathéodory en 1907. Si l'on note n la dimension de E, le théorème affirme qu'on peut utiliser des barycentres de p points en se bornant au cas p = n + 1 pour reconstituer toute l'enveloppe convexe. Ainsi dans un plan, étant donné A, on construit mentalement son enveloppe convexe en noircissant par la pensée tous les triangles à sommets dans A ; en dimension 3 on utiliserait des tétraèdres, et ainsi de suite.

Le théorème s'énonce précisément ainsi :

Théorème — Dans un espace affine de dimension n, l'enveloppe convexe d'un sous-ensemble A est l'ensemble des combinaisons convexes de familles de n + 1 points de A.

Une fois cet énoncé connu, il est facile d'en déduire un corollaire important :

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

(Alors que par exemple dans l'espace de Hilbert 2, de base hilbertienne (δn)n∈ℕ, la suiten/n)n∈ℕ et sa limite 0 forment un compact, dont l'enveloppe convexe n'est même pas fermée[2].)

Aspects algorithmiques[modifier | modifier le code]

En 2D[modifier | modifier le code]

Plusieurs algorithmes ont été inventés pour résoudre ce problème, leur complexité varie :

Dimensions d'ordres supérieurs[modifier | modifier le code]

Cette section ne cite pas suffisamment ses sources (septembre 2013). Pour l'améliorer, ajouter en note des références vérifiables ou les modèles {{Référence nécessaire}} ou {{Référence souhaitée}} sur les passages nécessitant une source.

Pour un ensemble fini de points, l'enveloppe convexe est un polyèdre convexe. Cependant, sa représentation n'est pas aussi facile que dans le cas du plan. Pour les dimensions strictement supérieures à 2, même si les arêtes du polyèdre sont connues, la construction des facettes n'est pas une tâche triviale. Un certain nombre d'algorithmes sont quand même connus pour la dimension 3, mais aussi dans le cas général.[réf. nécessaire]

Références[modifier | modifier le code]

  1. Marcel Berger, Géométrie [détail des éditions], Prop. 11.1.8.4, tome 3, p. 26 dans l'édition de 1978.
  2. (en) Charalambos D. Aliprantis (en) et Kim C. Border, Infinite Dimensional Analysis: A Hitchhiker's Guide, Springer,‎ 2007 (lire en ligne), p. 185.
  3. (en) Michael Ian Shamos, Computational Geometry : thèse de doctorat, université Yale,‎ 1975
    (en) Michael Ian Shamos et Dan Hoey, « Closest-point problems », dans Proceeding of 16th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles, IEEE Computer Society Press,‎ 1975 (lire en ligne), p. 151-162.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]

(en) Convex Hull Algorithms, Applet Java en 3D