Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleBounding the radii of balls meeting every connected component of semi-algebraic sets
Author(s) Saugata Basu, Marie-Françoise Roy
TypeArticle in Journal
AbstractWe 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 semi-algebraic 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.
KeywordsSemi-algebraic sets, Bit-sizes
URL http://www.sciencedirect.com/science/article/pii/S0747717110000891
JournalJournal of Symbolic Computation
Pages1270 - 1279
Translation No
Refereed No