1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Commented Feb 10, 2023 at 20:29
  • 1
    $\begingroup$ @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)$. $\endgroup$
    – Lee Mosher
    Commented Feb 10, 2023 at 20:33
  • $\begingroup$ @LeeMosher Thank you! Or alternatively we can take the left & right halves of the unit circle centered at the origin, I think. $\endgroup$ Commented Feb 10, 2023 at 22:15

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Yes, thank you! This was my initial thought also. Then I thought I had a counterexample so I was confused, but after reading your answer, I realize that my counterexample was wrong! I think at this level of generality it is unlikely to get something more specific. $\endgroup$
    – Ralph
    Commented Feb 10, 2023 at 20:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .