Three-dimensional polyhedra can be described by three polynomial inequalities

Abstract

Bosse et al. conjectured that for every natural number $d\ge 2$ and every $d$-dimensional polytope $P$ in ${\Re }^d$ there exist $d$ polynomials $p_0(x),...,p_{d-1}(x)$ satisfying $P=\{x\in {\mathbb{R}}^d:p_0(x)\ge 0,>...,p_{d-1}(x)\ge 0\}.$ We show that for dimensions $d\le 3$ even every $d$-dimensional polyhedron can be described by $d$ polynomial inequalities. The proof of our result is constructive.

23 pages, 8 figures

References in corpus (2)

• Structured Semidefinite Representation of Some Convex Sets
• Representing elementary semi-algebraic sets by a few polynomial inequalities: A constructive approach