Description of polygonal regions by polynomials of bounded degree

2010/02/04 by Gennadiy Averkov, Averkov, Gennadiy, Christian Bey +1
Computer Science · Mathematics · #14P10 #52A10 #52B11 #Advanced Combinatorial Mathematics #Algebraic Geometry (math.AG) #Computational Geometry and Mesh Generation #FOS: Mathematics #Metric Geometry (math.MG) #Point processes and geometric inequalities #math.AG #math.MG #msc:14P10 #msc:52A10 #msc:52B11

paper · pdf · doi:10.48550/arxiv.1002.0941

arxiv created 2010/02/04 · openalex publication_date 2010/02/04 · arxiv updated 2010/02/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that every (possibly unbounded) convex polygon P in R² with m edges can be represented by inequalities p₁ ≥ 0,...,p_n ≥ 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) ≤ n(m,k) ≤ (1+ε_m) s(m,k) with s(m,k):=max \m/k,log₂ m\ and ε_m → 0 as m → ∞. This choice of n is asymptotically best possible. An analogous result on representing the interior of P in the form p₁ > 0,..., p_n > 0 is also given. For k ≤ m/log₂ m these statements remain valid for representations with arbitrary polynomials of degree not exceeding k.

Citations

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

Related

• Polynomial inequalities representing polyhedra
• Polynomial convexity with degree bounds
• On the representation of polyhedra by polynomial inequalities
• Representing simple d-dimensional polytopes by d polynomials
• Unbounded convex polygons as polynomial images of the plane