This has been tormenting me for weeks. Given a set of $N$ points in $\mathbb{R}^d$, $N > d$, I want to find the largest ball enclosed within their convex hull, and I want to know which facets of the hull are tangent to said ball. Some relevant facts from my particular situation: the points are all centered at zero (if $x$ is a point then $-x$ is also a point), and the radius $r$ is such that $\frac{1}{N} \leq r^2 \leq \frac{1}{d} $.
I can't express the hull in terms of linear inequalities, because in my case there's likely to be exponentially many inequalities (in the number of points). I know how to check whether a particular point is in the convex hull of my set, but not whether a whole ball is contained. If I am able to find the maximum-radius ball, then I also don't know how to efficiently find the faces tangent to it, i.e. without searching over the exponentially many faces.
Here's a randomly generated example in $d=2$ case ... I'm trying to find the starred points efficiently as $d$ gets too large to check with brute force:
I would be immensely grateful for any help.