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.



Is a given point in the interior of the convex hull of a given finite collection of points?
Take your linear program and add the objective function **max** $x$, and the inequalities $\lambda\_i - x \geq 0$. If the point is on the exterior, the optimum solution has $x=0$. Otherwise, there is a solution with $x > 0$. 


