# Join vs. Convex Hull

Consider two subsets of $$\mathbb{R}^n$$, $$A$$ and $$B$$. Their join is the set of line segments connecting a point in $$A$$ to s point in $$B$$. That is, $$x\in\text{Join}(A,B)$$ if and only if $$x=\lambda a+(1-\lambda) b$$, where $$a\in A$$, $$b\in B$$, and $$\lambda\in[0,1]$$.

The convex hull of the union of $$A$$ and $$B$$ is the set of all convex combinations of points in $$A$$ and $$B$$, without the restriction that one point is in $$A$$ and one in $$B$$. In other words, $$x\in\text{Convex Hull}(A\cup B)$$ if and only if $$x=\sum_{i=1}^N\lambda_i x_i$$, where $$x_i\in A\cup B$$, $$\lambda_i\in[0,1]$$ and $$\sum_{i=1}^N \lambda_i=1$$.

Obviously, $$\text{Join}(A,B)$$ is a subset (weakly) of $$\text{Convex Hull}(A\cup B)$$. It is also quite easy to show that if $$A$$ and $$B$$ are convex sets, then $$\text{Join}(A,B)=\text{Convex Hull}(A\cup B)$$. However, convexity of $$A$$, $$B$$ is not necessary for this equality. In particular, it is easy to construct examples where $$\text{Join}(A,B)=\text{Convex Hull}(A\cup B)$$, but where $$A$$ or $$B$$ (or both) is not convex.

I was wondering if there is a necessary and sufficient condition for equality between the join of sets in $$\mathbb{R}^n$$ and the convex hull of their union. In addition, any references or results on the relationship between the join and the convex hull are appreciated.

• I'm having trouble imagining any nontrivial examples of this phenomenon. Could you please provide an example where the join equals the hull of the union but $A$ and $B$ are not both convex and neither $A$ nor $B$ is contained in the hull of the other? Commented Feb 10, 2023 at 20:29
• @diracdeltafunk: In $\mathbb R^2$, let $A$ be the left half of the circle of radius $1$ centered on $(-1,0)$, and let $B$ be the right half of the circle of radius $1$ centered on $(1,0)$. Commented Feb 10, 2023 at 20:33
• @LeeMosher Thank you! Or alternatively we can take the left & right halves of the unit circle centered at the origin, I think. Commented Feb 10, 2023 at 22:15

If $$\operatorname{join}(A,B) = \operatorname{hull}(A \cup B)$$ then $$\operatorname{join}(A,B)$$ is convex. Conversely, if $$\operatorname{join}(A,B)$$ is convex, then since $$A \cup B \subseteq \operatorname{join}(A,B)$$, we will have $$\operatorname{hull}(A \cup B) \subseteq \operatorname{join}(A,B)$$, and thus $$\operatorname{join}(A,B) = \operatorname{hull}(A \cup B)$$.
So, $$\operatorname{join}(A,B) = \operatorname{hull}(A \cup B)$$ iff $$\operatorname{join}(A,B)$$ is convex. We can write this condition out explicitly:
$$\operatorname{join}(A,B) = \operatorname{hull}(A \cup B)$$ iff $$\forall a_1, a_2 \in A \; \forall b_1, b_2 \in B \; \forall t_1, t_2, s \in [0,1]\\ \exists a \in A \; \exists b \in B \; \exists t \in [0,1]\\ s(t_1 a_1 + (1-t_1) b_1) + (1-s)(t_2 a_2 + (1-t_2)b_2) = ta + (1-t)b.$$