# An equivalent condition of the intersection of convex hulls of two compact sets being empty

I came across the following problem where $$A$$ and $$B$$ are two compact sets in $$\mathbb{R}^n$$ ('compact' here means 'closed and bounded'). We need to show that there exists a nonzero vector $$\mathbf{a}\in \mathbb{R}^n$$ and a scalar $$b\in \mathbb{R}$$ such that: $$\mathbf{a}^{\top}\mathbf{x}-b \leq -1 ~ \forall \mathbf{x} \in A \text{ and } \mathbf{a}^{\top}\mathbf{x}-b \geq 1 ~ \forall \mathbf{x} \in B,$$ if and only if the intersection of the convex hull of $$A$$ and the convex hull of $$B$$ is empty.

I think it is similar to the Separating hyperplane theorem of convex sets. However, I cannot figure out where the $$-1$$ and $$1$$ comes from. Maybe the proof of this statement is far from the Separating hyperplane theorem? Any useful suggestions are appreciated.

• It is just the usual separation theorem you can find in Rudin's FA. A simple transformation can be used to get $-1$ and $+1$. Oct 4, 2021 at 11:34
• Thanks. Could you explain more about the 'simple transformation' to get -1 and +1, which I'm still confused about? Oct 4, 2021 at 12:06

To prove this from standard version of a separation theorem you can do the following: If $$a^{T}x-b \leq \alpha$$ on $$A$$ and $$a^{T}x-b \geq \beta$$ on $$B$$ with $$\beta >\alpha$$ apply the map $$f(t)=\frac 2 {\beta-\alpha} t-1-\frac {2\alpha} {\beta-\alpha}$$ to these inequalities. Since $$f$$ is increasing the inequalities remain valid after aplying $$f$$ to both sides.
• Thanks a lot. But I have two more questions. First, when applying the map to both sides, $a^{T}x-b$ is also changed, so that it is not the original inequality. Second, the standard version of separation theorem is about two convex sets, while here $A$, $B$ are arbitrary compact sets and we are talking about their convex hulls. Sorry to bother but I'm fresh in this area. It would be appreciated if you could reply. Oct 4, 2021 at 13:29
• When you apply $f$ to $a^{T}x-b$ you get $a'^{T}x-b'$ for some $a',b'$. Can you figure out what $a'$ and $b'$ are ? I am using the fact that convex hulls of compact sets in $\mathbb R^{n}$ are themselves compact. This is proved in Rudin's book. Once you know this you can apply the separation theorem to the convex hulls of $A$ and $B$. @Arthur556 Oct 4, 2021 at 23:15