Polytope dual

Le concept de polytope dual est étroitement lié à la notion de convexité. De plus, il permet d'associer des entités d'un polyèdre à celle de son dual de manière biunivoque.

Soit x un point de $\mathbb{R}^n$, on définit le demi-espace $H_x^+$ par $\displaystyle y \in R^n, <x,y> \leq 1$

ou <> désigne le produit scalaire. Soit P un polytope dont les sommets sont les points v_i de $\mathbb{R}^n$. Alors le polytope dual P ^* est le sous-ensemble de $\mathbb{R}^n$ définit par l'intersection de tous les demi-espaces $H_{v_i}^+$.

Pour un polyèdre P, P ^* est alors aussi un polyèdre, et on a alors les associations suivantes: la face duale v ^* d’un sommet v de P est une face du polyèdre P ^* normale à la droite (Ov). De même, le dual d’une arête e = (v1; v2) est l’arête égale à l’intersection des duaux des 2 sommets. Enfin, le dual d’une face f de P est un sommet.

Soit x un point de l'intérieur relatif d'une face t de P, alors on définit l'ensemble K_x par $\displaystyle K_x = {y \in R^n; \forall x' \in P; <x',y> \leq 1 et <x, y>}$

K_x est alors appelée face dual de t (puisque K_x est constant pour tout x dans l'intérieur relatif de t).

Plus généralement, si a est une face de b dans le polyèdre P, b ^* est une face de a ^* dans le polyèdre P^*.

Références

• (en) J. Dattorro, Convex optimization & Euclidean distance geometry, Lulu.com (2006), ISBN 978-1847280640.

Voir aussi

• Dual d'un polyèdre.