Details:
Title  Bounding the radii of balls meeting every connected component of semialgebraic sets  Author(s)  Saugata Basu, MarieFrançoise Roy  Type  Article in Journal  Abstract  We prove an explicit bound on the radius of a ball centered at the origin which is guaranteed to contain all bounded connected components of a semialgebraic set S ⊂ R^k defined by a weak sign condition involving s polynomials in Z [ X_1 , … , X_k ] having degrees at most d , and whose coefficients have bitsizes at most τ . Our bound is an explicit function of s , d , k and τ , and does not contain any undetermined constants. We also prove a similar bound on the radius of a ball guaranteed to intersect every connected component of S (including the unbounded components). While asymptotic bounds of the form 2^τ d^O ( k ) on these quantities were known before, some applications require bounds which are explicit and which hold for all values of s , d , k and τ . The bounds proved in this paper are of this nature.  Keywords  Semialgebraic sets, Bitsizes  ISSN  07477171 
URL 
http://www.sciencedirect.com/science/article/pii/S0747717110000891 
Language  English  Journal  Journal of Symbolic Computation  Volume  45  Number  12  Pages  1270  1279  Year  2010  Note  MEGA’2009  Edition  0  Translation 
No  Refereed 
No 
