Intersection of convex hulls of two disjoint sets

66 Views Asked by At

Suppose that I have a finite set in $\mathbb R^n$, $A:=\{x_1,\ldots,x_n\}$. I want a condition on this set such that $co(S) \cap co(T) = \emptyset$ for any $S,T \subset A$ with $S \cap T = \emptyset$, where $co(S)$ denotes the convex hull of $S$.

I had thought that if the set is convexly independent meaning that no $x_i$ is a convex combination of other $x_j$'s, then I may have hope. But that is clearly not true. I wanted some reasonably standard conditions that I could look up that guarantee the property I mentioned. Any help would be appreciated. Thanks!

1

There are 1 best solutions below

1
On BEST ANSWER

Your property is equivalent to affine independence.

Suppose the $n$ points are affinely dependent, i.e., they live in some $(n-2)$-dimensional affine subspace. Then the $n-1$ vectors $y_1=x_1-x_n,\ldots, y_{n-1}=x_{n-1}-x_n$ are linearly dependent, i.e., there are real numbers $c_i$, not all zero, such that $c_1y_1+\cdots +c_{n-1}y_{n-1}=0$. This gives us disjoint sets $I_+:=\{\,i\mid c_i>0\,\}$ and $I_-:=\{\,i\mid c_i<0\,\}$ such that not both are empty. Thus $s_+:=\sum_{i\in I_+}c_i$ and $s_-:=-\sum_{i\in I_-}c_i$ are both non-negative but not both zero. Wlog $s_+\ge s_-$. Let $c_n=s_+-s_-$. Then $$\sum_{i\in I_+}\frac{c_i}{s_+} x_i=\sum_{i\in I_-}\frac{|c_i|}{s_+} x_i + \frac{c_n}{s_+}x_n,$$ showing that $$\operatorname{co}\{\,x_i\mid i\in I_+\,\}\cap\operatorname{co}\{\,x_i\mid i\in I_-\cup\{n\}\,\}\ne\emptyset.$$

Conversely, if two convex hulls of disjoint subsets have a point in common, we can reverse the above procedure to obtain a linear dependence between differences, thereby showing that the $x_i$ live in an $(n-2)$-dimensional affine subspace.