Problem: Given points $u,v_1,\dots,v_n\in\mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1,\dots,v_n.$
This can be done efficiently by linear programming (time polynomial in $n,m$) in the obvious way. I have two questions:
Is there a different (or more efficient algorithm) for this? If not, there ought to be a simple reduction from linear programming to the above problem as well. What is it?
Are there interesting families of instances for which the problem can be solved significantly faster than by means of linear programming, e.g., nearly linear time in $m+n$.