Representing simple d-dimensional polytopes by d polynomials

DOI10.1007/S10107-009-0280-YMaRDI QIDQ623364zbMATH OpenOpenAlexFDO

Authors Gennadiy Averkov, Martin Henk

Publication date 14 February 2011

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0709.2099

zbMATH Keywords

polynomial representation of polytopes

Mathematics Subject Classification ID

(n)-dimensional polytopes (52B11) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Abstract: A polynomial representation of a convex d-polytope P is a finite set {p_1(x),...,p_n(x)} of polynomials over E^d such that P=setcond{x in E^d}{p_1(x) ge 0 {for every} 1 le i le n}. By s(d,P) we denote the least possible number of polynomials in a polynomial representation of P. It is known that d le s(d,P) le 2d-1. Moreover, it is conjectured that s(d,P)=d for all convex d-polytopes P. We confirm this conjecture for simple d-polytopes by providing an explicit construction of d polynomials that represent a given simple d-polytope P.

Recommendations

• The representation of polyhedra by polynomial inequalities
• scientific article; zbMATH DE number 5956571
• Polynomial inequalities representing polyhedra
• Minimal polynomial descriptions of polyhedra and special semialgebraic sets
• Three-dimensional polyhedra can be described by three polynomial inequalities

Cites work

• scientific article; zbMATH DE number 1726532 (Why is no real title available?)
• scientific article; zbMATH DE number 5302815 (Why is no real title available?)
• scientific article; zbMATH DE number 1201576 (Why is no real title available?)
• scientific article; zbMATH DE number 852103 (Why is no real title available?)
• scientific article; zbMATH DE number 914533 (Why is no real title available?)
• scientific article; zbMATH DE number 236540 (Why is no real title available?)
• scientific article; zbMATH DE number 3296351 (Why is no real title available?)
• Algebraic surfaces: with appendices by S. S. Abhyankar, J. Lipman and D. Mumford.
• Algorithms in real algebraic geometry
• Approximating convex bodies by algebraic ones
• Approximation of convex surfaces by algebraic surfaces
• Lectures on Polytopes
• Minimale Erzeugung von Positivbereichen
• On basic semialgebraic sets
• Polynomial inequalities representing polyhedra
• Polynomial representations of polyhedra
• Reducing inequalities with bounds
• Representing polynomials by positive linear functions on compact convex polyhedra
• Stability index of real varieties
• The representation of polyhedra by polynomial inequalities
• Three-dimensional polyhedra can be described by three polynomial inequalities

Cited in

(10)

• Fleck's congruence, associated magic squares and a zeta identity
• On polytopes that are simple at the edges
• Simple 0/1-polytopes
• Reproducing kernel Hilbert spaces for parametric partial differential equations
• Polynomial representations of polyhedra
• scientific article; zbMATH DE number 5956571 (Why is no real title available?)
• The representation of polyhedra by polynomial inequalities
• Minimal polynomial descriptions of polyhedra and special semialgebraic sets
• Polynomial inequalities representing polyhedra
• Three-dimensional polyhedra can be described by three polynomial inequalities

Describes a project that uses

Uses Software

• SINGULAR

This page was built for publication: Representing simple \(d\)-dimensional polytopes by \(d\) polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q623364)