Join vs. Convex Hull

60 Views Asked by At

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.

1

There are 1 best solutions below

1
On

Here is a silly, mostly unhelpful answer.

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