Combinaison convexe

En géométrie affine, une combinaison convexe de certains points est un barycentre de ces points avec des coefficients tous positifs[1]. L'ensemble des combinaisons convexes de ces points est donc leur enveloppe convexe.

Définition modifier

 
Étant donnés trois points   dans un plan, le point P est une combinaison convexe des trois points, tandis que Q ne l'est pas (Q est seulement une combinaison barycentrique des trois points).

Soit E un espace affine réel (c'est-à-dire que les scalaires sont les nombres réels). Si   et   sont des points de E, une combinaison convexe des   est[1] un point   de la forme

 

  sont des réels positifs de somme 1.

Problème du point extrême modifier

Le problème du point extrême consiste à déterminer si un point P0 est ou non une combinaison convexe de points Pi, 1 ≤ in. Dobkin et Reiss[2] ont montré que ce problème avait une complexité linéaire, en O(n), dans   et  . Megiddo[3] a montré que la complexité était linéaire en dimension finie, dans   avec d fini.

La résolution se ramène à savoir s'il existe une droite (dans  ), un plan (dans  ) ou un hyperplan (dans  , d > 3) passant par P0, tel que tous les points Pi sont du même côté de la droite, du plan ou de l'hyperplan. Cela revient donc au problème de séparation : séparer un ensemble de points par un hyperplan.

Dans le plan, la recherche peut se faire de la manière suivante[3]. On effectue une transformation affine de sorte que P0 ait pour coordonnées (0 ; 0) et P1(0 ; 1) ; de ce fait, la droite de séparation, si elle existe, ne peut pas être l'axe des y. Le point Pi a pour coordonnées (xi, yi).

La droite cherchée passe par P0, l'origine, et a donc pour équation :

y = ax, ce qui s'écrit également si x est non nul y/x = a.

Cette droite délimite deux demi-plans d'équation (y < ax) et (y > ax).

Si P0 n'est pas dans l'enveloppe convexe, alors tous les points sont dans le même demi plan, c'est-à-dire que tous les points doivent être au-dessus de la droite (puisqu'au moins un point, P1, l'est). On doit donc avoir pour tout i

yi > axi

soit

  • si xi > 0, alors yi/xi > a ;
  • si xi < 0, alors yi/xi < a.

On a donc la condition nécessaire et suffisante pour que a existe, c'est-à-dire pour que P0 soit hors de l'enveloppe convexe :

 

Notes et références modifier

  1. a et b Aviva Szpirglas, Algèbre L3 : Cours complet avec 400 tests et exercices corrigés [détail de l’édition] Définition 4.28
  2. (en) D. P. Dobkin et S. P. Reiss, « The complexity of linear programming », Theoretical Computer Science, no 11,‎
  3. a et b (en) Nimrod Megiddo, « Linear-time algorithms for linear programming in   and related problems », SIAM Journal on Computing, vol. 4,‎ , p. 766-769 (DOI 10.1137/0212052, MR 721011, lire en ligne)

Article connexe modifier