Enveloppe convexe

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.

Sommaire

1 Définition et propriétés élémentaires
- 1.1 Description en termes de barycentres
2 Le cas de la dimension finie : un théorème de Carathéodory
3 Aspects algorithmiques
- 3.1 En 2D
- 3.2 Dimensions d'ordres supérieures
4 Références
5 Liens externes

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 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

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

Proposition — L'enveloppe convexe de $A$ est l'ensemble des barycentres à coefficients positifs ou nuls de familles de points de $A$ .

Lorsque $E$ est un espace vectoriel (ou un sous-espace affine d'un espace vectoriel), on en déduit alors facilement que 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

a i

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

Article détaillé : Théorème de Carathéodory (géométrie).

L'énoncé qui précède peut être amélioré en dimension finie, comme remarqué par Constantin Carathéodory en 1907. Si 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 barycentres à coefficients positifs ou nuls 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.

Aspects algorithmiques

En 2D

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

Marche de Jarvis
Parcours de Graham
Heuristique de Akl-Toussaint

Dimensions d'ordres supérieures

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 connus, 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érences

↑ Marcel Berger, Géométrie [détail des éditions], Prop. 11.1.8.4, tome 3, p. 26 dans l'édition de 1978.

Liens externes

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

v · Ensemble convexe Outils et résultats fondamentaux : Enveloppe convexe • Adhérence, intérieur et frontière d'un convexe • Projection sur un convexe fermé • Séparation des convexes • Points remarquables à la frontière d'un convexe • Polytope • Théorème de Krein-Milman • Lemme de Farkas Géométrie combinatoire : Théorème de Carathéodory • Théorème de Radon • Théorème de Helly Géométrie métrique : Courbe de largeur constante • Théorème des quatre sommets Algorithmes de géométrie convexe : Approche polyédrique • Marche de Jarvis • Parcours de Graham • Théorème optimisation/séparation Optimisation linéaire : Optimisation linéaire • Algorithme du simplexe • Génération de colonnes
Interactions géométrie-analyse	Théorème de Hahn-Banach • Jauge
Analyse convexe	Articles principaux : Ensemble convexe • Fonction convexe Outils et résultats fondamentaux : Conditions de Kuhn-Tucker • Inégalité de Jensen Algorithmique : Méthodes de points intérieurs
Utilisations de la convexité	Inégalités de convexité : Inégalité arithmético-géométrique • Inégalité de Hölder Analyse fonctionnelle : Espace localement convexe • Théorème du point fixe de Schauder Localisation de zéros de polynômes : Théorème de Gauss-Lucas Théorie des nombres : Théorème de Minkowski

Portail de la géométrie

Catégories :

Analyse convexe
Géométrie convexe
Algorithmique et convexité
Optimisation combinatoire

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Enveloppe convexe de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

Enveloppe Convexe — 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… … Wikipédia en Français
Enveloppe — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « enveloppe », sur le Wiktionnaire (dictionnaire universel) En acoustique musicale, l enveloppe sonore… … Wikipédia en Français
convexe — [ kɔ̃vɛks ] adj. • 1370; lat. convexus ♦ Courbe, arrondi vers l extérieur. ⇒ bombé, renflé; convexité. Lentille, miroir convexe. Géogr. Rive convexe, qui forme une avancée de terre (dans une courbe de la rivière). ♢ Surface, courbe convexe,… … Encyclopédie Universelle
Enveloppe supérieure — En mathématiques, l enveloppe supérieure d une famille de fonctions à valeurs réelles est la fonction dont la valeur en un point est le supremum (ou borne supérieure) des valeurs prises par ces fonctions en ce point. Sommaire 1 Définition 2… … Wikipédia en Français
Ensemble convexe — Pour les autres sens du mot « convexe », voir convexité. Un objet géométrique est dit convexe lorsque, chaque fois qu on y prend deux points A et B, le segment [A,B] qui les joint y est entièrement contenu. Ainsi un cube plein, un… … Wikipédia en Français
Polytope convexe — Ensemble convexe Pour les autres sens du mot « convexe », voir convexité. Un objet géométrique est dit convexe lorsque, chaque fois qu on y prend deux points A et B, le segment [A,B] qui les joint y est entièrement contenu. Ainsi… … Wikipédia en Français
Polyèdre convexe — Ensemble convexe Pour les autres sens du mot « convexe », voir convexité. Un objet géométrique est dit convexe lorsque, chaque fois qu on y prend deux points A et B, le segment [A,B] qui les joint y est entièrement contenu. Ainsi… … Wikipédia en Français
Points et parties remarquables de la frontière d'un convexe — Face à un polyèdre convexe de l espace de dimension 3, qu il soit familier comme un cube ou plus compliqué, on sait spontanément reconnaître les points où le convexe est « pointu », ses sommets, puis subdiviser les points restants entre … Wikipédia en Français
Points et parties remarquables de la frontiere d'un convexe — Points et parties remarquables de la frontière d un convexe Face à un polyèdre convexe de l espace de dimension 3, qu il soit familier comme un cube ou plus exotique, on sait spontanément reconnaître des points où le convexe est… … Wikipédia en Français
Adherence, interieur et frontiere d'un convexe — Adhérence, intérieur et frontière d un convexe Dans le cas particulier de parties convexes d un espace vectoriel topologique, les opérateurs topologiques élémentaires d adhérence ou intérieur préservent la convexité. Sous une réserve technique… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Enveloppe convexe

Sommaire