Check if a point is in the interior of the convex hull of some other points in high dimensions, and lower-bounding the largest enclosed ball [closed]

Question

Given $m$ points $P=\{p_0, p_1, ..., p_m\}$ in high dimensions (e.g. 100), it is known that computing (or even representing) their convex hull $\text{conv}(P)$ is generally intractable due to the exponential dependence on dimensions. In this case, I wonder:

1. Is there an efficient algorithm to check whether some other given point $\tilde{p}$ is an interior point in the convex hull (i.e. there is a small ball centered at $\tilde{p}$ and lies in $\text{conv}(P)$)? I know we can construct a linear programming problem to check if a point lies inside the convex hull, but my question here is to further check if the convex hull has "volume" and if $\tilde{p}$ lies in its interior.
2. Following 1, can we compute or efficiently lower-bounding the largest enclosed (inscribed) ball centered at $\tilde{p}$ and lies in $\text{conv}(P)$?

I'm an amateur in geometry and I appreciate any potential solutions or suggestions. Thank you for your time!

The same question posted on MathSE.

Answer 1

x is not in the interior of conv(P) iff there is an affine function $u(y) = a+ b\cdot y$ such that $u(x)\le 0$ and $u(p_i)\ge0$ for $i=0,\ldots,m$. If this problem has no feasible solution, then x is in the interior.

Alternatively, x is in the relative interior of conv(P) iff for some t > 0, $x = \sum_{i=0}^m a_i p_i$, where $\sum_i a_i = 1$, and $t\le a_i \le 1$. Maximimzing t subject to these constraints is a linear program.