5
$\begingroup$

The convex hull of a set $C$ is $$conv(C) = \{\theta_1x_1 + \theta_2x_2 + \cdots + \theta_k x_k: x_i \in C,\theta_i \ge 0, \sum \theta_i = 1, k=1, 2, \ldots \}$$

I am wondering why it is not enough to take $k=2$ in the definition. Is there a simple example of a set $C$ for which the set $$\{\theta_1x_1 + \theta_2x_2: x_1,x_2 \in C,\theta_1, \theta_2 \ge 0, \theta_1 +\theta_2 = 1\}$$ is not convex?

$\endgroup$
3
  • $\begingroup$ I'd imagine you could prove it by induction, if you can get the $k=3$ case to follow from the $k=2$ one. $\endgroup$
    – Chappers
    Sep 17 '15 at 12:34
  • $\begingroup$ I suggest you read en.wikipedia.org/wiki/… $\endgroup$
    – Augustin
    Sep 17 '15 at 12:39
  • $\begingroup$ Take $C$ to be a set of $3$ different points, then your set is an empty triangle it is not convex. conv(C) you can get by applying your procedure iteratively. I.e. applying it to the empty triangle you get filled triangle which is convex. $\endgroup$ Sep 17 '15 at 12:39
2
$\begingroup$

No the two definitions are not equivalent!

For a very simple counter example let $x_1 \neq x_2 \neq x_3 \in \mathbb R^2$ (and also assume they are not collinear). Then our counterexample is the set $C=\{x_1,x_2,x_3\}$. I will denote by $conv2(C)$ your second definition of a "convex hull". Then graphically we get (blame my graphic skills for the rounded corners):

convex hull

$\endgroup$
1
  • 1
    $\begingroup$ Ah! So we need larger $k$s to be able to take combinations of our combinations. Got it. $\endgroup$
    – Fequish
    Sep 17 '15 at 13:03
1
$\begingroup$

Take for $C$ three points $x_1, x_2, x_3$ in the plane that form a triangle, i.e. the three points are not lying on the same line.

If you take for $$conv(C) = \{\lambda x_i + (1-\lambda) x_j : \lambda \in [0,1], \ i,j \in \{1,2,3\} \}$$ you'll get for $conv(C)$ the set of segments joining the $3$ points, i.e. the "line triangle", not the interior point of the triangle. This is not what is expected for the convex hull.

This is why you need to take convex combinations of finite points, not only two points.

However, it is true that you can get a finite convex combination by iterating a finite number of time convex combination with only two points.

$\endgroup$

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.