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

preprint2009arXivOpen access

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 ss polynomials in $\mathbbm{Z}[X_1, ..., X_k]$ having degrees at most dd, and whose coefficients have bitsizes at most ττ. Our bound is an explicit function of s,d,ks, 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 SS (including the unbounded components). While asymptotic bounds of the form 2τdO(k)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,ks, d, k and ττ. The bounds proved in this paper are of this nature.

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 reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.