# Radius of the largest enclosed ball in the convex hull of an algebraic variety

Let $\mathcal{V}\subset\mathbb{R}^n$ be a real compact algebraic variety. Let $\mathcal{V}^c$ be the convex hull of $\mathcal{V}$ and let us assume that $\mathcal{V}^c$ has nonzero n-dimensional Lesbegue measure.

Question: Are there any known lower bounds for the inner radius (=radius of largest enclosed ball) of $\mathcal{V}^c$ (for instance in terms of the polynomials that generate $\mathcal{V})$.

Informal remark: I am especially interested in cases when $\mathcal{V}$ is generated by only a few polynomials of "low degree".

• "Inner radius" = radius of largest enclosed ball? – Joseph O'Rourke Apr 16 '15 at 11:19
• yes, I have edited the question – Michał Oszmaniec Apr 16 '15 at 11:59
• you can edit the subject too... – Dima Pasechnik Apr 16 '15 at 15:10
• What about the polynomial $x_1^2 + \dots + x_n^2 - \epsilon$? It seems like a pretty "good" polynomial from most perspectives, but your radius is just $\epsilon$. How do you hope to exclude this sort of thing? – Will Sawin Apr 19 '15 at 1:33
• Thanks for the comment. Notice however that I expicitely mentioned "..in terms of polynomials that generate $\mathcal{V}$". In the problems I am studying (they have origin in quantum information) I have different varieties that can be specified by different polynomials. The point is to be able to get the lower bounds for the inner radius of $\mathcal{V}^c$ in terms of these polynomials – Michał Oszmaniec Apr 19 '15 at 18:34

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

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.
• Moreover, for me it would seam to be more natural to first approximate $\mathcal{V}^c$ via spectrahedron (or its projection) and the use semidefinite programing. – Michał Oszmaniec Apr 19 '15 at 18:49