Three-dimensional polyhedra can be described by three polynomial inequalities

Convex sets in (2) dimensions (including convex curves) (52A10) Convex sets in (3) dimensions (including convex surfaces) (52A15) Inequalities and extremum problems involving convexity in convex geometry (52A40) (n)-dimensional polytopes (52B11)

Abstract: Bosse et al. conjectured that for every natural number

d g e 2

and every

d

-dimensional polytope

P

in

e a l^{d}

there exist

d

polynomials

p_{0} (x), ..., p_{d - 1} (x)

satisfying

P = x i n m a t h b b R^{d} : p_{0} (x) g e 0, > ..., p_{d - 1} (x) g e 0 .

We show that for dimensions

d l e 3

even every

d

-dimensional polyhedron can be described by

d

polynomial inequalities. The proof of our result is constructive.

Review text

The authors show that every convex polygon in \(\mathbb{R}^2\) and every convex polyhedron in \(\mathbb{R}^3\), bounded or unbounded, can be fully described by two or three polynomial inequalities, respectively. This confirms, for dimensions \(d=2\) and \(3\), a conjecture in [\textit{H. Bosse, M. Grötschel} and \textit{M. Henk}, Math. Program. 103, No.~1 (A), 35--44 (2005; Zbl 1140.90528)], according to which every convex \(d\)-polytope in \(\mathbb{R}^d\) can be represented by \(d\) polynomial inequalities.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Three-dimensional polyhedra can be described by three polynomial inequalities

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