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*, 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.

A better source is

Stephen Boyd, Lieven Vandenberghe. *Convex optimization*. Cambridge. 2004.
(PDF download book.)

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.