Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
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

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer

Quickhull uses divide and conquer a la quicksort. I believe its worst-case complexity is $O(n^2)$, but could be wrong.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.