I was reading the wikipedia article about Minkowski addition. There's a proposition there:

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?

  • 1
    $\begingroup$ $A$ and $B$ aren't convex at all! $\endgroup$ – Olivier Bégassat Aug 13 '13 at 23:34
  • 1
    $\begingroup$ $A+B$ is not convex because it includes $(4,1)$? I think you have the wrong idea of what "convex" means. $\endgroup$ – 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$

  • $\begingroup$ Thanks, I got it now. I think I misunderstood the Convex Hull. I thought ConvexHull(A) is a subset of A, which is set of vertices of a Convex polygon covering all points in A. $\endgroup$ – saeedn Aug 14 '13 at 17:25

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.