would number of extreme points of convex polygon shrink by union?

76 Views Asked by At

Given two Convex polygon $A$, $B$, denote their number of extreme points as $N(A), N(B)$.

One can obtain a bigger convex polygon by union $A, B$, and find the convex hull denote $C:= CH(A\cup B)$.

what's the relationship between $N(C)$ vs $N(A) + N(B)$, my gut feeling is $N(C) \leq N(A) +N(B)$ ? and what's the lower bound of $N(C)$ in the sense of $N(A), N(B)$?

and do the results generalize to non-convex polygon? and also do the result generalizes to convex polytope?

1

There are 1 best solutions below

1
On BEST ANSWER

We are going to show $N(C) \le N(A) + N(B)$ in general.

For any $p \in C$, we have either $p \in A \cup B$ or $\not\in A \cup B$.

Case I - $p \not\in A\cup B$.

In this case, I claim

there is an $\alpha \in (0,1)$, $a \in A$ and $b \in B$ such that $p = \alpha a + (1-\alpha) b$

To see why this is true, consider the set of points $$C' \stackrel{def}{=} \{ \alpha a + (1-\alpha) b : \alpha \in [0,1], a \in A, b \in B \}$$

It is not hard to see

  • $A \subset C'$ (by taking $\alpha= 1$) and $B \subset C'$ (by taking $\alpha = 0$).
  • $C'$ is convex.
  • Every convex set contains $A$ and $B$ contains $C'$.

Since by definition $C$ is the smallest convex set containing $A$ and $B$, this forces $C = C'$.

This implies we can find an $\alpha \in [0,1], a \in A, b \in B$ such that $p = \alpha a + (1-\alpha) b$. Now $\alpha$ cannot be $0$ because $p \not\in B$ and cannot be $1$ because $p \not\in A$. This justifies above claim.

Next, choose a small positive $\epsilon < \min( \alpha, 1 - \alpha )$, we find $p$ is the mid point of two points $(\alpha \pm \epsilon ) a + (1 - \alpha \mp \epsilon ) b \in C$. This means $p$ cannot be an extreme point.

Case II - $p \in A \cup B \implies p \in A \lor p \in B$.

If $p \in A$ but not an vertex of $A$, it is not an extreme point of $A$ and hence cannot be an extreme point of the larger set $C$. By a similar argument, when $p \in B$ but not an vertex of $B$, $p$ cannot be an extreme point of $C$.

Combine these two cases, we find there are at most $N(A) + N(B)$ candidates of extreme points of $C$. Namely, the vertices of $A$ and $B$. From this, we can deduce $$N(C) \le N(A) + N(B)$$