Write the convex hull of the points $(0,0), (1,1), (2,0) \in \mathbb R^2$ as the set of solutions to a finite number of inequalities.

The convex hull of $x_1, \ldots, x_n \in \mathbb R^n$ is defined as the set $\{\lambda_1x_1 + \ldots + \lambda_n x_n : \sum_{i=1}^{n} \lambda_n = 1, \lambda_i \ge 0\}$.

I see that the convex hull of our points is $X = \{\lambda_1 (0,0) + \lambda_2 (1,1) + \lambda_3 (2,0) : \lambda_1 + \lambda_2 + \lambda_3 = 1, \lambda_i \ge 0\}$ however I've had no luck in expressing this set as a finite number of inequalities. How is this done ?


You just have to draw a diagram of the region. You will see that it is the intersection of three half-planes. For instance, one of the half-planes, corresponding to the line from $(0,0)$ to $(1,1)$, contains all points $(x,y)$ such that $x \ge y$: this is one of your inequalities. I will let you find the other two.

  • $\begingroup$ Is this formal enough ? I mean, how do I see every point in this region lies in convex hull ? $\endgroup$
    – Shuzheng
    Sep 6 '14 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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