# Deciding membership in a convex hull

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:

1. 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?

2. 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$.

-
Btw it's not true that you can solve this in time poly in n and m. such an algorithm would be as trongly polynomial time algorithm for linear programming, which is as yet unknown. what is true is that you can solve it in polynomial time, but the running time involves terms relating to the bit complexity of the problem: en.wikipedia.org/wiki/Linear_programming#Algorithms –  Suresh Venkat Jan 12 '10 at 8:38

It isn't just that you can do the problem with linear programming. The reduction to linear programming actually shows that the convex hull problem is equivalent by dualization to the feasible-point problem in linear programming. In other words, you are asking whether there exist coefficients $\alpha_1,\ldots,\alpha_n \ge 0$ such that $$u = \alpha_1 v_1 + \alpha_2 v_2 + \cdots + \alpha_n v_n.$$ The vector of coefficients $\vec{\alpha}$ is a feasible point in a general linear programming problem, and you are asking whether a feasible point exists. Thus the problem can't be any harder or easier than linear programming.
Quickhull uses divide and conquer a la quicksort. I believe its worst-case complexity is $O(n^2)$, but could be wrong.