Enveloppe convexe

{{#ifeq:||Un article de Ziki, l'encyclopédie libre.|Une page de Ziki, l'encyclopédie libre.}}

{{#invoke:Bandeau|ébauche}}

Fichier:ConvexHull.png
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

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 E le cadre géométrique où l'on se place.

Modèle:Théorème

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.

Modèle:Théorème

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

Par exemple, Modèle:Math() = ∅.

Description en termes de barycentres

Dans la suite de cette section, on supposera que E est un espace affine réel. On peut alors énoncer<ref>Modèle:Berger2, Prop. 11.1.8.4, tome 3, Modèle:P. dans l'édition de 1978.</ref> :

Modèle:Théorème

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

<math>x=\sum_{i=1}^p \lambda_i a_i</math>, expression dans laquelle Modèle:Math est un entier, les Modèle:Math sont dans A, les coefficients Modèle:Math sont réels positifs et de somme <math>\sum_{i=1}^p \lambda_i=1.</math>

Le cas de la dimension finie : un théorème de Carathéodory

Modèle:Article détaillé

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 :

Modèle:Théorème

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

Modèle:Théorème

(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<ref>Modèle:Ouvrage.</ref>.)

Aspects algorithmiques

En 2D

Fichier:Cvx hull splx steps ND.gif
Construction itérative de l'enveloppe convexe d'un nuage de points par un algorithme de pseudo Quickhull.

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 :

Dimensions d'ordres supérieurs

Modèle:Section à sourcer Pour un ensemble fini de points, l'enveloppe convexe est un polyèdre convexe. Cependant, Modèle:Refnec

Références

<references/>

Voir aussi

Articles connexes

Lien externe

{{#invoke:Langue|indicationDeLangue}} Convex Hull Algorithms, Applet Java en 3D

Modèle:Palette

Modèle:Portail