On the Representation of Polyhedra by Polynomial Inequalities

Please always quote using this URN: urn:nbn:de:0297-zib-6826

A beautiful result of Bröcker and Scheiderer on the stability index of basic closed semi-algebraic sets implies, as a very special case, that every $d$-dimensional polyhedron admits a representation as the set of solutions of at most $d(d+1)/2$ polynomial inequalities. Even in this polyhedral case, however, no constructive proof is known, even if the quadratic upper bound is replaced by any bound depending only on the dimension. Here we give, for simple polytopes, an explicit construction of polynomials describing such a polytope. The number of used polynomials is exponential in the dimension, but in the 2- and 3-dimensional case we get the expected number $d(d+1)/2$.

Metadaten
Author:	Martin Grötschel, Martin Henk
Document Type:	ZIB-Report
Tag:	polyhedra and polytopes; polyhedral combinatorics; polynomial inequalities; semialgebraic sets
MSC-Classification:	14-XX ALGEBRAIC GEOMETRY / 14Pxx Real algebraic and real analytic geometry / 14P10 Semialgebraic sets and related spaces
	52-XX CONVEX AND DISCRETE GEOMETRY / 52Bxx Polytopes and polyhedra / 52B11 n-dimensional polytopes
	52-XX CONVEX AND DISCRETE GEOMETRY / 52Bxx Polytopes and polyhedra / 52B55 Computational aspects related to convexity (For computational geometry and algorithms, see 68Q25, 68U05; for numerical algorithms, see 65Yxx) [See also 68Uxx]
	90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
	90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Date of first Publication:	2002/03/27
Series (Serial Number):	ZIB-Report (02-15)
ZIB-Reportnumber:	02-15
Published in:	Appeared in: Discrete & Computational Geometry 29 (2003) 485-504 under the title: "The Representation of Polyhedra by Polynomial Inequalities"

Open Access