Dans toute cette page on suppose que le corps de base est ℝ. A désigne un espace affine réel.
Nous avons déjà rencontré la notion de convexité (voir par exemple).

Segment

Un 'segment' de A est caractérisé par la donnée de deux points P et Q.
C'est l'ensemble des barycentres des systèmes ((P,α),(Q,β)) où α et β sont de même signe.
Un tel segment se note [PQ].
Les deux remarques qui suivent résultent du principe d'homogénéité des barycentres :
Un segment

Parties convexes

On dit qu'une partie B de A est 'convexe' si chaque fois qu'elle contient deux points, elle contient tout le segment joignant ces deux points.
Une partie convexe Une partie non convexe
image: http://fr.wikipedia.org/wiki/Ensemble_convexe image: http://fr.wikipedia.org/wiki/Ensemble_convexe

Exemples

Tout cela est évident sauf peut-être le dernier point, mais si M1 et M2 sont situés dans le même demi-espace par rapport à un hyperplan H tout point G du segment [M1M2] vérifie :
OG = α O M 1 + β O M 2 α + β
où O est un point quelconque de H et α, β sont deux scalaires positifs.
G appartient donc au même demi-espace que M1 et M2.
Voici une appliquette mettant en évidence la convexité d'une ellipse.
Déplacez deux points A et B à l'intérieur de l'ellipse.
Le segment [AB] sera traçé qui doit se trouver entièrement à l'intérieur de l'ellipse.

Enveloppe convexe

Il résulte de la définition que l'intersection d'une famille quelconque (finie ou infinie) de parties convexes, est encore une partie convexe.
Pour toute partie X de A il existe des parties convexes contenant X (par exemple A lui-même).
L'intersection de tous les convexes contenant X est donc un convexe contenant X et c'est évidemment le plus petit de ceux-ci.
On appelle ce convexe l'appelle "l'enveloppe convexe" de X.

Cas des ensembles finis

Supposons que X={P0,P1, ... ,Pn} soit un ensemble fini de n+1 points. L'enveloppe convexe de X sera, en particulier contenue dans la variété linéaire engendrée par ces n+1 points.
Cependant, dans ce cas particulier il est facile de caractériser l'enveloppe convexe :
L'enveloppe convexe de X est exactement l'ensemble des barycentres des systèmes ((P11), (P22), ,(P1n)) où tous les λi sont > 0.
La preuve est simple. Par le théorème d'associativité, l'ensemble des tels barycentres est convexe. Or tout ensemble convexe contenant X doit contenir ces barycentres.

Image: http://fr.wikipedia.org/wiki/Enveloppe_convexe

Café Python

Voici un programme qui utilise l'algorithme de Graham pour déterminer l'enveloppe convexe d'un système fini de points.

Et voici le résultat (fichier hull.png) :