En mathématiques, plus précisément en géométrie, l'enveloppe convexe d'un ensemble de points est le plus petit ensemble convexe qui les contient tous.
Dans un plan, l'enveloppe convexe peut être comparée à la région dé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 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 l'on notera le cadre géométrique où l'on se place.
Cette définition a un sens, puisqu'il existe au moins une partie convexe de qui contient , à savoir 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.
Développé de façon plus détaillée, ce résultat caractérise l'enveloppe convexe comme l'unique sous-ensemble de qui vérifie les trois conditions suivantes :
est convexe ; est inclus dans ; si est un sous-ensemble convexe de contenant , alors est inclus dans .
Par exemple, .
Description en termes de barycentres
Dans la suite de cette section, on supposera que est un espace affine réel. On peut alors énoncer, Prop. 11.1.8.4, tome 3, dans l'édition de 1978. :
Autrement dit : les éléments de l'enveloppe convexe de sont exactement les points de qu'on peut écrire sous la forme : , expression dans laquelle est un entier, les sont dans , les coefficients sont réels positifs et de somme
Le cas de la dimension finie : un théorème de Carathéodory
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 la dimension de , le théorème affirme qu'on peut utiliser des barycentres de points en se bornant au cas pour reconstituer toute l'enveloppe convexe. Ainsi dans un plan, étant donné , on construit mentalement son enveloppe convexe en noircissant par la pensée tous les triangles à sommets dans ; en dimension 3 on utiliserait des tétraèdres, et ainsi de suite.
Le théorème s'énonce précisément ainsi :
Une fois cet énoncé connu, il est facile d'en déduire un corollaire important :
(Alors que par exemple dans l'espace de Hilbert ℓ, de base hilbertienne (δ), la suite (δ/n) et sa limite 0 forment un compact, dont l'enveloppe convexe n'est même pas fermée..)
Aspects algorithmiques En 2D
Le calcul de l'enveloppe convexe d'un ensemble de points est un problème classique en géométrie algorithmique. Plusieurs algorithmes ont été inventés pour résoudre ce problème, leur complexité varie : marche de Jarvis, en , étant le nombre de points de l'enveloppe convexe ; algorithme de Chan, en ; parcours de Graham, en ; heuristique de Akl-Toussaint ; utilisation du diagramme de Voronoï., en : les points de l'enveloppe convexe définissent des cellules de Voronoï ouvertes, il suffit de détecter ces cellules et de relier les germes des cellules adjacentes.
3D et dimensions d'ordres supérieurs
En dimension , pour un ensemble fini de points, l'enveloppe convexe est un polyèdre convexe dont chacun des éléments qui le constitue est un Simplexe de dimension . En dimension par exemple, l'enveloppe convexe est un maillage triangulaire. Pour les dimensions strictement supérieures à , le processus de construction est plus complexe car certains algorithmes nécessitent de vérifier à chaque étape la convexité de l'ensemble.
Références
Voir aussi Articles connexes
Enveloppe convexe fermée Problème du cercle minimum Surface de sustentation Théorème de Krein-Milman Théorème de Tverberg
Liens externes Convex Hull Algorithms, Applet Java en 3D
Catégorie:Analyse convexe Catégorie:Géométrie convexe Catégorie:Algorithmique et convexité Catégorie:Optimisation combinatoire