Abstract
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 polynomials in $\mathbbm{Z}[X_1, ..., X_k]$ having degrees at most , and whose coefficients have bitsizes at most . Our bound is an explicit function of 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 (including the unbounded components). While asymptotic bounds of the form on these quantities were known before, some applications require bounds which are explicit and which hold for all values of and . The bounds proved in this paper are of this nature.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.