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
    0 references
    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
    0 references
    polynomial representation of polytopes
    0 references

    Identifiers