1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ How would we define the extreme points of $Z$ here? In the plane I suppose we pick the outer most points but is there a more formal definition? $\endgroup$
    – user320757
    Mar 8 '16 at 9:01
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.