Enveloppe convexe

Imaginez des clous plantés dans une planche, puis un élastique tendu autour d'eux. Quand on le relâche, l'élastique entoure les clous les plus extérieurs et laisse les autres à l'intérieur. La région ainsi délimitée donne l'image de l'enveloppe convexe.

Cette enveloppe comble tous les creux : deux points qu'elle contient peuvent toujours être reliés par un segment qui reste entièrement dedans. Elle est aussi la plus petite région ayant cette propriété et contenant tous les points de départ.

Soit S un ensemble de points d'un espace vectoriel réel. Un ensemble est convexe lorsque, pour toute paire de ses points, il contient le segment entier qui les relie. L'enveloppe convexe de S, notée $\mathrm{conv}(S)\backslash operatorname\{conv\}(S)$, est l'intersection de tous les ensembles convexes qui contiennent S. Elle est donc convexe, contient S et est incluse dans tout convexe contenant S.

Une combinaison convexe de points x₁, …, x_n de S est une moyenne pondérée dont les coefficients sont positifs ou nuls et ont pour somme 1. L'enveloppe convexe rassemble exactement toutes les combinaisons convexes finies de points de S :

Si S est fini, son enveloppe est un polytope : un polygone dans le plan lorsqu'elle a une aire non nulle, et un polyèdre convexe en dimension 3. Dans un espace de dimension d, le théorème de Carathéodory précise que chaque point de l'enveloppe s'écrit avec au plus d + 1 points de S.

Dans le plan, considérons trois points : A de coordonnées (0 ; 0), B de coordonnées (4 ; 0) et C de coordonnées (2 ; 3). On veut vérifier que le point P de coordonnées (2 ; 1) appartient à leur enveloppe convexe.

1. Prenons les trois coefficients 1/3, 1/3 et 1/3.
2. Ils sont positifs et leur somme vaut 1.
3. La moyenne des abscisses vaut (0 + 4 + 2) / 3 = 2.
4. La moyenne des ordonnées vaut (0 + 0 + 3) / 3 = 1.

On obtient donc $P=\frac{1}{3}A+\frac{1}{3}B+\frac{1}{3}C=(2,1)P=\backslash frac\{1\}\{3\}A+\backslash frac\{1\}\{3\}B+\backslash frac\{1\}\{3\}C=(2,1)$. Le point P est une combinaison convexe de A, B et C : il appartient au triangle ABC, qui est leur enveloppe convexe. Pour contrôler le résultat, on peut refaire séparément les deux moyennes de coordonnées.

Pour entourer un nuage de points, on calcule son enveloppe convexe et l'on ne conserve que les points extrêmes. Une boîte englobante est préférable si l'on veut seulement des bornes parallèles aux axes et un calcul plus simple.

En géométrie algorithmique, l'enveloppe sert de contour initial pour accélérer certaines recherches de distances, d'intersections ou de séparation. Si les creux du nuage comptent, ce contour convexe est trop grossier et il faut choisir une représentation non convexe.

Dans un problème de mélanges, chaque combinaison convexe représente une moyenne pondérée admissible. L'enveloppe décrit alors toutes les valeurs accessibles, à condition que les poids soient positifs ou nuls et totalisent 1.

Enveloppe convexe et ensemble convexe. Un ensemble est convexe s'il contient chaque segment joignant deux de ses points. Son enveloppe convexe est une construction : elle ajoute le minimum de points nécessaire pour rendre convexe un ensemble qui ne l'est pas.

Enveloppe convexe et boîte englobante. La boîte englobante suit des directions imposées, souvent celles des axes. Pour les trois points A, B et C de l'exemple, elle est le rectangle de sommets (0 ; 0), (4 ; 0), (4 ; 3) et (0 ; 3), tandis que l'enveloppe convexe est le triangle ABC.

Points alignés. Dans le plan, l'enveloppe de plusieurs points alignés est un segment, ou un seul point s'ils coïncident. Elle n'est pas un polygone d'aire positive ; il faut conserver sa dimension réelle.

Ensemble vide. Il n'existe aucune combinaison convexe finie de points du vide. On adopte habituellement une enveloppe convexe vide, mais il faut vérifier la convention du cadre employé.

Fermeture non automatique. L'enveloppe convexe d'un ensemble non fermé peut elle-même ne pas être fermée. Si le problème exige aussi tous les points limites, il faut prendre l'enveloppe convexe fermée, c'est-à-dire la fermeture de l'enveloppe convexe.

Rôle exact de Carathéodory. Dire qu'un point de l'enveloppe est une combinaison convexe découle de la caractérisation de l'enveloppe. Le théorème ajoute la borne d + 1 dans un espace de dimension d ; dans le plan, trois points suffisent.

La fiche Combinaison convexe détaille les poids positifs ou nuls de somme 1 qui engendrent chaque point de l'enveloppe.

La fiche polytope prolonge la construction en dimension supérieure et décrit l'objet obtenu à partir d'un ensemble fini.

L'article Les enjeux de la géométrie algorithmique replace le calcul des enveloppes parmi les problèmes et méthodes de cette discipline.