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

Details:

   
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
ISSN0747-7171
URL http://www.sciencedirect.com/science/article/pii/S0747717110000891
LanguageEnglish
JournalJournal of Symbolic Computation
Volume45
Number12
Pages1270 - 1279
Year2010
NoteMEGA’2009
Edition0
Translation No
Refereed No
Webmaster