1
$\begingroup$

What is the easiest way to prove that the intersection of finite number of convex hulls is a convex hull?

It seems to be an easy statement to prove, but still I can not get even the idea of proving. So, I would be grateful even for an idea behind the prove.

Edit: Information pulled from comments: We are talking about in the plane, and a "convex hull" here is a convex polygon - that is, the convex hull of a finite set of points.

$\endgroup$
15
  • $\begingroup$ The intersection of any collection of convex sets is convex, and every convex set is the convex hull of itself. $\endgroup$ – Angina Seng Sep 10 '17 at 16:01
  • $\begingroup$ Yeah, this question is only interesting if by "convex hull" you mean "convex hull of a finite set." $\endgroup$ – Thomas Andrews Sep 10 '17 at 16:02
  • $\begingroup$ @LordSharktheUnknown, ok. I feel it intuitively. And now I want to prove it. It is the reason I asked it here. $\endgroup$ – hellomates Sep 10 '17 at 16:02
  • 1
    $\begingroup$ To show the first half of that (that the intersection of a collection of convex sets is convex), consider any two points in the intersection. By definition, they're in each set in the collection, and since those sets are convex then the line between them is in each set in the collection, so.. $\endgroup$ – Steven Stadnicki Sep 10 '17 at 16:02
  • $\begingroup$ @ThomasAndrews, why is not it interesting for an infinite number of convex hulls? $\endgroup$ – hellomates Sep 10 '17 at 16:03
1
$\begingroup$

Lemma: In the plane, a set $X$ is the convex hull of a finite set of points if and only if $X$ is convex and it is either a single point, a line segment, or can be written as the union of a finite number of triangles (where a triangle includes its boundary and interior.)

The we need to prove:

  1. The intersection of two convex sets is convex.
  2. The intersection of two triangles is a convex hull (where an empty set is considered the convex hull on an empty set.)
  3. The intersection of a line segment and a triangle is either a point, a line segment, or empty.
  4. The intersection of a line segment and a line segment is either a point, a line segment, or empty.

From this, you get that if $X$ and $Y$ are both convex hulls of finite sets, then $X\cap Y$ is a convex hull of a finite set.

Then you get your full result by induction.

Each of these parts are relatively easy to show, with (2) requiring the most details.


There are two possible definitions of "convex hull" here. There is a "usual definition," but there are reasons in this question to think that your question is asking about another definition.

Let $X\subseteq \mathbb R^n$. The the "convex hull of $X$" is the smallest convex set that contains $X$. In particular, this can be written as the set of points:

$$H(X)=\left\{x\in\mathbb R^n\mid x=t_1x_1+t_2x_2+\cdots+t_nx_n,\,x_i\in X,\,t_i\geq 0, \sum t_i=1\right\}$$

Now, one might define "a convex hull" to be any $H(X)$, but (1) that's uniteresting, because then "a convex hull" is the same as a convex set - if $Y$ is a convex set, then $H(Y)=Y$. Also, with this definition of "convex hull," you don't need the "finite" part of your question.

On the other hand, one might define "a convex hull" as any $H(X)$ where $X$ is finite. In that definition, the nature of $H(X)$ is that it's boundaries are all 'flat.' But it is also tricky to prove that a finite intersection of such hulls is still such a hull.

From your comment above, particularly the reference to polygons, it does seem like you mean this second type: $H(X)$ for some finite set $X$.

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