Minimal polynomial descriptions of polyhedra and special semialgebraic sets

Abstract: We show that a

d

-dimensional polyhedron

S

in

e a l^{d}

can be represented by

d

-polynomial inequalities, that is,

S = x i n e a l^{d} : p_{0} (x) g e 0, > ..., p_{d - 1} (x) g e 0

, where

p_{0}, ..., p_{d - 1}

are appropriate polynomials. Furthermore, if an elementary closed semialgebraic set

S

is given by polynomials

q_{1}, ..., q_{k}

and for each

x i n S

at most

s

of these polynomials vanish in

x

, then

S

can be represented by

s + 1

polynomials (and by

s

polynomials under the extra assumption that the number of points

x i n S

in which

s

q_{i}

's vanish is finite).

Recommendations

Cited in

(6)

This page was built for publication: Minimal polynomial descriptions of polyhedra and special semialgebraic sets