The join of two convex sets is convex?

Question

Let A and B be convex subsets of $\Bbb R^n$. The join of A and B is the set of all $\vec x$ such that $\vec x$ lies on a line segment with one endpoint in A and the other in B. I am wondering how to show that the join of A and B is a convex set.

Answer 1

Let $p_1$ and $p_2$ belong to the join of $A$ and $B.$ $$\text {Let } q=x p_1+(1-x)p_2 \text { with } x\in [0,1].$$ There exist $a_1\in A$ and $b_1\in B$ and $r_1\in [0,1]$ with $$p_1=r_1 a_1+(1-r_1)b_1.$$ There exist $a_2\in A$ and $b_2$ in $B$ and $r_2\in [0,1]$ with $$p_2=r_2 a_2+(1-r_2)b_2.$$ Since $A$ and $B$ are convex, we have $$A\supset \{c a_1+(1-c)a_2 :c\in [0,1]\}$$ $$\text {and }\quad B\supset \{db_1+(1-d)b_2:d\in [0,1]\}.$$ So if we can find $c,d,e\in [0,1]$ such that $$\bullet \;q=e[c a_1+(1-c)a_2]+(1-e)[d b_1+(1-d)b_2],$$ then $q$ belongs to the join of $A$ and $B.$ $$\text {Now }\; q=x p_1+(1-x)p_2=x[r_1a_1+(1-r_1)b_1]+(1-x)[r_2a_2+(1-r_2)b_2].$$ I will leave it to you to show that there do exist $c,d,e\in [0,1]$ such that $$x r_1=e c.$$ $$(1-x)r_2=e(1-c).$$ $$x(1-r_1)b_1=(1-e)d.$$ $$(1-x)(1-r_2)=(1-e)(1-d).$$ Then the equation $\bullet$ is satisfied.

Answer 2

Basically, this comes down to the following algebra exercise. We take convex combinations to represent any $x$ in the join: $$x_1=\alpha_1 a_1 + \beta_1 b_1$$ $$x_2=\alpha_2 a_2 + \beta_2 b_2$$ and then make a convex combination of those: $$\kappa x_1+\gamma x_2=\kappa \alpha_1 a_1 + \kappa \beta_1 b_1 + \gamma \alpha_2 a_2 + \gamma \beta_2.$$ Then, we need to represent this as: $$\kappa \alpha_1 a_1 + \kappa \beta_1 b_1 + \gamma \alpha_2 a_2 + \gamma \beta_2=\alpha(\kappa_1 a_1 + \gamma_1 a_2)+\beta(\kappa_2 b_1 + \gamma_2 b_2)$$ to show that any convex sum of two points in our join is writable as a convex sum of two points $\kappa_1 a_1 + \gamma_1 a_2\in A$ and $\kappa_2 b_1 + \gamma_2 b_2$. Then, we need $$\alpha \kappa_1 = \alpha_1 \kappa$$ $$\alpha \gamma_1 = \alpha_2\gamma$$ $$\beta \kappa_2= \beta_1\kappa$$ $$\beta \gamma_2= \beta_2\gamma$$ which looks pretty awful, where the left hand variables are the ones we need and the right hand are fixed. To make this clear, I should note how I have named variables: I used $\alpha$ and $\beta$ to indicate any convex sum "crossing" from set $A$ to set $B$. I used $\kappa$ and $\gamma$ to indicate convex sums within $A$ or $B$ respectively, or somehow "in this direction". The subscripts indicate which of a nested convex sum the indices belong to, with no subscript for the outer sum. It is taken that $\alpha_i+\beta_i=1$ and $\kappa_i+\gamma_i=1$.

However, we can sum the first two equations to get one equation and last two equations to get another, noting that $\kappa_1+\gamma_1=1$ and $\kappa_2+\gamma_2=1$. This gives $$\alpha=\alpha_1\kappa + \alpha_2\gamma$$ $$\beta=\beta_1\kappa + \beta_2\gamma.$$ Easily, we then divide out the first two equations by $\alpha$ to get $$\kappa_1=\frac{\alpha_1\kappa}{\alpha_1\kappa + \alpha_2\gamma}$$ $$\gamma_1=\frac{\alpha_2\gamma}{\alpha_1\kappa + \alpha_2\gamma}$$ and similarly $$\kappa_2=\frac{\beta_1\kappa}{\beta_1\kappa + \beta_2\gamma}$$ $$\gamma_2=\frac{\beta_2\gamma}{\beta_1\kappa + \beta_2\gamma}.$$ You can convince yourself that each group of these equations actually forms the coefficients of a convex combination (i.e. are non-negative and sum to $1$) and can check that they satisfy the desired equality. This algebra is basically saying that a tetrahedron is the join of a pair of disjoint edges, and that this suffices for convexity.

Answer 3

Using defintion of the convext set, to prove, given any two points in join of two set, the line segment connecting the given two points lies entirely inside the join.

You have six cases:

1. Both given points are in set A;
2. Both given points are in set B;
3. one point is in set A, and other point is in set B
4. one point is in set A, other point is in the join but not in set A or B;
5. one point is in set B, other point is in the join but not in A and B;
6. Both points are in the join but not in A and B.

Case 1 and 2 are true from the definition of the convex set. Case 3 is true due to the defintion of join of two sets. For case 4, let a be the point in the set A, let other point e in the join but not in the set A or B, so we know there is a point u in set A and point v in set B, that e is in the line segment connecting u and v. Now draw a line from a to u, extend the line av both ends to intersect the set A boundary at p and q. now draw a line segment from p to e and q to e, we have a triangle with the vetices p, q, e. any point o on the segment ae can be drawn a line from b to o and extends to hit the line segment pg in the set A. so line segment ae is in the join.

case 5 is similar to case 4.

case 6 is a interesting case. name these two points as o and p. we know there is a point i in A and j in B, that o is in the line segment ij. We know there is a point k in A and point l in B, such that p is on the line segment kl. if the line segment ij and kl do not intersect, then we draw line ik in set A and line segment jl in set B. Four line segments form a quardrangle. Any point inside the quadrangle is on some line segment wiht one point on ik and other point on jl. So line segment op is in the join.

if the line ij and kl intersect, then we draw line segment il and jk, they both not interesect each other. line ij abd kl are the diagnoal lines of quadrangle formed by ik, il, jl, ki. Clearly, any point on the line segment op is inside this quadrangle. Any point on op can be on the line segemtn connecting a point on ik and a point on jl.

(drawing a picture would help)

Answer 4

A slightly more conceptual approach to the "the join of two segments is the tetrahedron of their ends" is to first show that the join is associative (which means manipulating three vertices instead of four, so easier), and that the convex hull of $s \cup \{a\}$ is the join of ${a}$ and the convex hull of $s$ (again, only two combinations to care about). Then

$$\begin{eqnarray} \mathrm{Join}([a, b], [c, d]) & = & \mathrm{Join}(\mathrm{Join}(\{a\}, \{b\}), \mathrm{Hull} \{c, d\}) \\ & = & \mathrm{Join}(\{a\}, \mathrm{Join}(\{b\}, \mathrm{Hull}\{c, d\})) \\ & = & \mathrm{Join}(\{a\}, \mathrm{Hull}\{b, c, d\}) \\ & = & \mathrm{Hull}\{a, b, c, d\} \end{eqnarray}$$