This is not a direct answer to your request for lower bounds; just some remarks. Sometimes the center of the largest enclosed ball is called the [*Chebyshev center*](http://en.wikipedia.org/wiki/Chebyshev_center), and you can find literature under that name. (But beware: the Chebyshev center sometimes means instead the center of the smallest enclosing ball.) Sometimes it is called the *ball center*. Your $\mathcal{V}^c$ is a convex set. Finding the largest enclosed ball in a convex set is a convex optimization problem. If you can approximate $\mathcal{V}^c$ with a convex polytope, then finding the biggest ball is a linear programming problem. E.g., these notes formulate that LP problem: [PDF download notes](http://www.ifor.math.ethz.ch/teaching/lectures/intro_ss11/Exercises/solutionEx11-12.pdf). A better source is > Stephen Boyd, Lieven Vandenberghe. *Convex optimization*. Cambridge. 2004. ([PDF download book](http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf).) They discuss the LP problem on p.148, and discuss the problem for a general convex set p.417ff. There they say, > Problem (8.16) is a convex optimization problem, since each function $g_i$ is the pointwise maximum of a family of convex functions of $x$ and $R$, hence convex. However, evaluating $g_i$ involves solving a convex maximization problem (either numerically or analytically), which may be very hard. In practice, we can find the Chebyshev center only in cases where the functions $g_i$ are easy to evaluate.