Bounding the radii of balls meeting every connected component of semi-algebraic sets |
| |
Authors: | Saugata Basu Marie-Françoise Roy |
| |
Affiliation: | 1. Department of Mathematics, Purdue University, West Lafayette, IN 47907, USA;2. IRMAR (URA CNRS 305), Université de Rennes 1, Campus de Beaulieu, 35042 Rennes, Cedex, France |
| |
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 semi-algebraic set S⊂Rk defined by a weak sign condition involving s polynomials in ZX1,…,Xk] 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τdO(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: | Semi-algebraic sets Bit-sizes |
本文献已被 ScienceDirect 等数据库收录! |
|