Polytope dual

Soit ${\displaystyle x}$ un point de ${\displaystyle \mathbb {R} ^{n}}$ (identifié à l'espace affine euclidien d'origine le vecteur nul) ; on définit le demi-espace ${\displaystyle H_{x}^{+}}$ par ${\displaystyle \{y\in R^{n},<x,y>\leq 1\}}$, où <> désigne le produit scalaire ; sa frontière, l'hyperplan ${\displaystyle H_{x}=\{y\in R^{n},<x,y>=1\}}$ est la polaire de x par rapport à la sphère unité. Soit P un polytope dont les sommets sont les points (non nuls) ${\displaystyle v_{i}}$ de ${\displaystyle \mathbb {R} ^{n}}$. Alors le polytope dual ${\displaystyle P^{*}}$ est le sous-ensemble de ${\displaystyle \mathbb {R} ^{n}}$ défini par l'intersection de tous les demi-espaces ${\displaystyle H_{v_{i}}^{+}}$.

Pour un polyèdre P, ${\displaystyle P^{*}}$ est alors aussi un polyèdre, et on a alors les associations suivantes : la face duale ${\displaystyle v^{*}}$ d’un sommet v de P est une face du polyèdre ${\displaystyle P^{*}}$ normale à la droite (Ov). De même, le dual d’une arête e = ${\displaystyle (v_{1};v_{2})}$ 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 ; on définit l'ensemble ${\displaystyle K_{x}}$ par${\displaystyle K_{x}=\{y\in R^{n};\forall x'\in P;<x',y>\leq 1\ et\ <x',y>\leq <x,y>\}}$.

${\displaystyle K_{x}}$ est alors appelée face duale de t (puisque ${\displaystyle 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, ${\displaystyle b^{*}}$ est une face de ${\displaystyle a^{*}}$ dans le polyèdre ${\displaystyle P^{*}}$.

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

• Dual d'un polyèdre
• Ensemble polaire (extension du concept à un ensemble quelconque)