Description of polygonal regions by polynomials of bounded degree

Abstract

We show that every (possibly unbounded) convex polygon $P$ in $R^2$ with $m$ edges can be represented by inequalities $p_1\ge 0,...,p_n\ge 0,$ where the $p_i$'s are products of at most $k$ affine functions each vanishing on an edge of $P$ and $n=n(m,k)$ satisfies $s(m,k)\le n(m,k)\le (1+{\epsilon }_m)s(m,k)$ with $s(m,k):=\max \{m/k,{\log }_{2}m\}$ and ${\epsilon }_m\to 0$ as $m\to \infty$. This choice of $n$ is asymptotically best possible. An analogous result on representing the interior of $P$ in the form $p_1>0,...,p_n>0$ is also given. For $k\le m/{\log }_{2}m$ these statements remain valid for representations with arbitrary polynomials of degree not exceeding $k$.

References in corpus (2)

• Representing elementary semi-algebraic sets by a few polynomial inequalities: A constructive approach
• Representing simple d-dimensional polytopes by d polynomials