1
$\begingroup$

Let $\operatorname{conv}(a_1,\ldots,a_m)$ denote the convex hull of $\{a_1,\ldots,a_n\}$. Let $P = \operatorname{conv}(a_1,\ldots,a_p)$ and $Q = \operatorname{conv}(b_1,\ldots,b_q)$ be two convex sets in $\mathbb R^n$.

Definition: An extreme point in a convex set $S$ in $\mathbb R^n$ is a point in $S$ which does not lie in any open line segment joining two points of $S$.

Let $\operatorname{ext}(P)$, $\operatorname{ext}(Q)$ denote the sets of extreme points of $P$, $Q$, respectively. Let $P + Q=\{ a+b : a \in P\text{ and } b\in Q \}$ be the Minkowski sum of $P$ and $Q$.

Question: What is $\operatorname{ext}(P+Q)$?

PS1: If not in general, is there any special case where the result is known and has a geometric interpretation?

PS2: I am not sure whether this question is of research level or not. If anybody thinks that this is not proper here please give the references and then vote to close. I have searched it in general but could not find any answer. Thanks in advance.

Improve this question
$\endgroup$
10
  • $\begingroup$ $ext(P+Q)$ will be $conv(\{a_i+b_j\mid 1\leq i\leq p, 1\leq j\leq q\})$. It is an exercise. $\endgroup$
    – Dima Pasechnik
    Commented May 16, 2015 at 6:33
  • 1
    $\begingroup$ It's true that $P+Q=\text{conv}(\{a_i+b_j\})$, but maybe some of those points are not extreme points? $\endgroup$
    – Anthony Quas
    Commented May 16, 2015 at 6:42
  • $\begingroup$ @AnthonyQuas : this is also an exercise :-) $\endgroup$
    – Dima Pasechnik
    Commented May 16, 2015 at 7:16
  • $\begingroup$ pictures speak for themselves here: en.wikipedia.org/wiki/Minkowski_addition $\endgroup$
    – Dima Pasechnik
    Commented May 16, 2015 at 7:22
  • $\begingroup$ @DimaPasechnik the points $a_i$ themselves are not critical points. So if I take $Q$ to be a point, your statement is not true. Do you mean to say the critical points are the sum of the critical points? $\endgroup$
    – Cusp
    Commented May 16, 2015 at 8:09

1 Answer 1

Reset to default
2
$\begingroup$

It consists of points $p=a_i+b_j$ for which there exists a linear functional $h$ such that $h$ attains its maximum on $A$ in unique point $a_i$ and on $B$ in unique point $b_j$.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .