# Convex hull of Minkowski sums

For all subsets S1 and S2 of a real vector-space, the convex hull of their Minkowski sum is the Minkowski sum of their convex hulls Conv(S1 + S2) = Conv(S1) + Conv(S2)

Where + is the Minkowski addition. But for a simple example it doesn't hold.

Assume $A = \{(0, 0), (1, 0), (1, 1), (0, 1)\}$ and $B=\{(3, 0), (4, 0), (4, 1), (3, 1)\}$. Then we have $A + B = \{(3, 0), (4, 0), (5, 0), (3, 1), (4, 1), (5, 1), (3, 2), (4, 2), (5, 2)\}$.

Both $A$ and $B$ are convex, thus they're equal to their convex hull, but $A + B$ is clearly not convex (because of vector (4, 1)).

Is this proposition has some conditions, or am I missing something in Minkowski addition here?

• $A$ and $B$ aren't convex at all! – Olivier Bégassat Aug 13 '13 at 23:34
• $A+B$ is not convex because it includes $(4,1)$? I think you have the wrong idea of what "convex" means. – Rahul Aug 14 '13 at 0:46

First picture contains $A$ and $B$ (black dots $\bullet$) and their convex hulls (blue and red). The second diagram depicts Minkowski sum of $A$ and $B$, the convex hull of Minkowski (magenta) and Minkowski sum of convex hulls of $A$ and $B$ (also magenta). Observe that $A \neq \mathrm{ConvexHull}(A)$, in other words, $A$ is not convex and neither is $B$, therefore $A+B$ does not need to be convex. On the other hand, indeed $\mathrm{ConvexHull}(A) + \mathrm{ConvexHull}(B) = \mathrm{ConvexHull}(A + B)$.
I hope this helps $\ddot\smile$