mg.metric geometry - Deciding membership in a convex hull

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.

Your second question then asks whether there are special cases of (the feasible point problem of) linear programming that are easier than the general case of linear programming. The answer is yes. For instance, the "quickhull" type algorithm that Steve Huntsman mentions performs well in any specific low dimension. It amounts to an algorithm for linear programming for the case that the coefficients are nonnegative and there are few equalities. You can also expect a faster algorithm (maybe even equivalent to quickhull) at the other extreme, when there are almost as many equalities as variables. And you can always think of new types of structured linear programming problems that are more convenient or faster, e.g. with a sparse matrix.

• Next gn.general topology - What is a monoidal metric space?
• Previous ct.category theory - What is a deformation of a category?