Is the intersection of convex hulls a convex hull?

Question

Given two finite sets of points, $X$ and $Y$, in $\mathbb R^d$ and assuming that $\text{conv}(X)\cap\text{conv}(Y)\neq\varnothing$.

I would guess that the intersection is a convex hull of some other finite set of points, $Z\in\mathbb R^d$ but is this actually true? How would I show it?

Answer 1

Let $Z$ be the set of extreme points of $\text{conv}(X) \cap \text{conv}(Y)$. Since the intersection of two convex sets is convex you have $$ \text{conv}(X) \cap \text{conv}(Y) = \text{conv}( \text{conv}(X) \cap \text{conv}(Y) ) = \text{conv}(Z).$$

Answer 2

To answer your question in the comment of the above answer (I don't have enough reputation to directly answer):

A point $x$ of a convex set $X$ is an extreme point if there is no $\lambda \in (0, 1)$ and no $y$, $y' \in X$ such that $x = \lambda y + (1 - \lambda) y'$.

This is from the bottom of page five of the notes on the relevant section of the module this question is from.

So to add to the answer above;

Clearly $conv(A) \cap conv(B) = conv(conv(A) \cap conv(B))$, as $conv(X)$ for a set $X$ is the smallest convex set containing $X$ (so if $X$ convex, as $X$ is the smallest set containing $X$ we get $conv(X) = X$).

I haven't wrote out a mathematical argument for $conv(conv(A) \cap conv(B)) = conv(Z)$ yet, but here's the intuition: In 3d, a convex hull has vertices (extreme points), lines between these vertices (convex combinations of two extreme points), faces between these vertices (convex combinations of points on the aforementioned lines) and the volume of the hull (convex combinations of points on the aforementioned faces).

Essentially, we can generate the convex hull of a set from it's extreme points as any non extreme points are convex combinations of the extreme points.