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.