Radius of largest sphere about a point in a convex hull

269 Views Asked by At

Let $C$ be a convex hull defined such that $C = \{Z \in \mathbb{R}^m | \alpha \le \sum_{k=1}^m Z_k \cdot \phi_k(x) \le \beta\}$ where $\phi_k$ are smooth functions, $x \in [0,1]$, and the $Z_k$'s are the components of $Z$. In practice, the $\phi_k$'s are discretized over $[0,1]$ which implies that numerically $C$ can be described by $n$ constraints where $n$ is the number of mesh points over $[0,1]$.

Let $\tilde{Z} \in C$ be an interior point of this convex hull. I am interested in finding the maximum radius such that a ball centered at $\tilde{Z}$ lies in $C$.

I know that I can easily formulate this as a convex optimization problem using cvx but I am wondering if there are analytical approaches for this problem. The only issue is that $m$ is let's say 200 and while I know cvx can handle high dimensions, having an analytical approach would make it simpler/faster.

I don't really have much background on convex analysis so suggestions are appreciated. Thanks!