Representing simple \(d\)-dimensional polytopes by \(d\) polynomials (Q623364)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Representing simple \(d\)-dimensional polytopes by \(d\) polynomials |
scientific article |
Statements
Representing simple \(d\)-dimensional polytopes by \(d\) polynomials (English)
0 references
14 February 2011
0 references
Each \(d\)-dimensional convex polytope \(P\) with \(m\) facets can be represented by minimal \(m\) linear inequalities. A generalization of such a \textit{H-representation} of \(P\) is the representation of \(P\) as the set \(P=\{x\in\mathbb{R}^d: p(x)\geq 0 \wedge p\in {\mathcal P}\}\) where \(\mathcal{P}\) is a finite set of polynomials of \(d\) variables. Let \(s(d,P)\) denote the least cardinality of \(\mathcal{P}\) representing \(P\). \textit{H. Bosse}, \textit{M. Grötschel} and the second author [Math. Program. 103, No. 1 (A), 35--44 (2005; Zbl 1140.90528)] have conjectured that \(s(d,P)=d\) for \(d\)-polytopes. In the present paper the authors prove this conjecture for the class of simple \(d\)-polytopes \(P\) (every vertex of \(P\) is contained in exactly \(d\) facets). The essence of the proof is the \textit{explicit construction} of \(d\) polynomials which represent a given \(d\)-polytope.
0 references
polynomial representation of polytopes
0 references