Suppose I have the convex hull $P$ of a finite collection of points in $\mathbb{R}^d,$ and I want to see whether a point $p$ is contained in $P.$ This is a standard (some would say *the* standard linear programming problem: we are determining whether $p = \sum_{i=1}^{V(p)} \lambda_i v_i,$ with $\lambda_i \geq 0,$ $\sum_i \lambda_i = 1.$ (sum being over the vertices of $P.$

But now, suppose I want to know whether $p$ is *strictly* contained in $P.$ (that is, whether $p$ is in the interior of $P$). Of course, this already assumes that $P$ has nonempty interior, but let's suppose we have some reason to know that. How do we check that? One way is to maximize $\lambda_i$ for $i=1, \dots, V(P)$ -- all the maxima should be positive. This is rather inefficient ($V(P)$ could be large). Another approach is to shrink $P$ slightly (that is, find a point in the interior, say the barycenter of the vertices, call it the origin, shrink the vertices by $1-\epsilon$, etc). This works, except that it is not clear what the right value of $\epsilon$ is.

I am probably missing something obvious.