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.