Description of polygonal regions by polynomials of bounded degree

被引:0
作者
Averkov, Gennadiy [1 ]
Bey, Christian [1 ]
机构
[1] Otto VonGuericke Univ Magdegurg, Fak Math, D-39106 Magdeburg, Germany
来源
MONATSHEFTE FUR MATHEMATIK | 2011年 / 162卷 / 01期
关键词
Gray code; Polygon; Polynomial; Semi-algebraic set; Theorem of Brocker and Scheiderer; GRAY CODES; INEQUALITIES; POLYHEDRA;
D O I
10.1007/s00605-010-0224-x
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We show that every (possibly unbounded) convex polygon P in R-2 with in edges can be represented by inequalities p(1) > 0,...,pn >= 0, where the pi'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 + epsilon(m))s(m, k) with s(m, k) := max{m/k, log(2) m} and epsilon(m) -> 0 as m -> infinity. 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 <= m / log(2) m these statements remain valid for representations with arbitrary polynomials of degree not exceeding k.
引用
收藏
页码:19 / 27
页数:9
相关论文
共 17 条
[1]  
ANDRADAS C, 1996, ERGEBNISSE MATH IHRE, V33
[2]  
[Anonymous], 1998, ERGEBNISSE MATH IHRE
[3]  
AVERKOV G, 2009, BEITRAGE ALGEBRA GEO, V50, P271
[4]  
AVERKOV G, 2009, MATH PROG A IN PRESS
[5]  
AVERKOV G, 2010, ARXIV10020921V1
[6]  
AVERKOV G, 2008, ARXIV08042134
[7]   Three-Dimensional Polyhedra Can Be Described by Three Polynomial Inequalities [J].
Averkov, Gennadiy ;
Henk, Martin .
DISCRETE & COMPUTATIONAL GEOMETRY, 2009, 42 (02) :166-186
[8]  
BERNIG A, 1998, THESIS U DORTMUND
[9]   Polynomial inequalities representing polyhedra [J].
Bosse, H ;
Grötschel, M ;
Henk, M .
MATHEMATICAL PROGRAMMING, 2005, 103 (01) :35-44
[10]  
Goddyn L, 2003, ELECTRON J COMB, V10