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.


closed as off-topic by Dima Pasechnik, Joonas Ilmavirta, Johannes Hahn, Stefan Kohl, Allen Knutson May 16 '15 at 11:09

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Dima Pasechnik, Joonas Ilmavirta, Allen Knutson
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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 May 16 '15 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 May 16 '15 at 6:42
  • $\begingroup$ @AnthonyQuas : this is also an exercise :-) $\endgroup$ – Dima Pasechnik May 16 '15 at 7:16
  • $\begingroup$ pictures speak for themselves here: en.wikipedia.org/wiki/Minkowski_addition $\endgroup$ – Dima Pasechnik May 16 '15 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 May 16 '15 at 8:09

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


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