Bounding the radii of balls meeting every connected component of semi-algebraic sets

Details Bounding the radii of balls meeting every connected component of semi-algebraic sets Bounding the radii of balls meeting every connected component of semi-algebraic sets

2009-11-06

arxiv.org/abs/0911.1340v1

J. Symbolic Comput. 45 (12):1270-1279, 2010

Computer Science

Symbolic Computation

11 pages

Scientific paper

We prove explicit bounds 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 \subset \mathbbm{R}^k$ defined by a quantifier-free formula involving $s$ polynomials in $\mathbbm{Z}[X_1, ..., X_k]$ having degrees at most $d$, and whose coefficients have bitsizes at most $\tau$. Our bound is an explicit function of $s, d, k$ and $\tau$, 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^{\tau 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 $\tau$. The bounds proved in this paper are of this nature.

Affiliated with

Also associated with

No associations

Rating

Bounding the radii of balls meeting every connected component of semi-algebraic sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bounding the radii of balls meeting every connected component of semi-algebraic sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounding the radii of balls meeting every connected component of semi-algebraic sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-391940