Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There were two parts to this question. I proved that the Minkowski sum of two sets $X+Y$ is convex whenever $X$ and $Y$ are convex, but how do I prove this second part? "Show by example that the Minkowski sum of two sets $X+Y$ may be convex even if neither $X$ nor $Y$ are convex."

share|improve this question

3 Answers 3

up vote 11 down vote accepted

$X=\mathbb{R}\setminus\{0\}$ is not convex but $X+X=\mathbb{R}$ is.

share|improve this answer
    
+1 Nice, clean example. If $a > 0$, one could also use $X = (-a,0) \cup (0,a)$. Then, $X+X = (-2a,2a)$. –  JavaMan Oct 9 '11 at 3:16
    
Sorry I still don't get it. Can u prove your example? Thank u so much~ –  xuan Oct 9 '11 at 5:47
    
What is there not to get? –  scineram Oct 9 '11 at 8:47
    
The example is really straight forward but I think I need a formal prove which I don't know how... –  xuan Oct 9 '11 at 9:54
    
@xuan: Take $x=-1\in X$, $y=1\in X$ and $t=1/2\in[0,1]$. Then $(1-t)x+ty=0\notin X$, so $X$ is not convex. $X+X=\mathbb{R}$ is the fact that any real number can be written as a sum of two nonzero real numbers; e.g. $1=1/2+1/2$ and $x=(x-1)+1$ for $x\neq 1$. That $\mathbb{R}$ is convex is an easy consequence of the definition of convexity. –  LostInMath Oct 9 '11 at 10:16

A stupid example: Let $X$ be any non-convex set and let $Y=\emptyset$. Then $X+Y=\emptyset$ is convex!

share|improve this answer
4  
But $Y$ is convex. –  scineram Oct 9 '11 at 8:46

If this helps you to understand the previous demonstration, you can think of the Minkowski Sum as a painting operation over the points of $X$ using $Y$ as a brush.

Now think of a convex set $X$ minus one interior point - and that is enough not to make it convex anymore.

This point or even small gaps will be painted over by the brush $Y$ standing in nearby points, if the brush is 'fat' enough. The resulting set will be made convex again.

Since a typical point of $X+Y$ will be covered by different points of the brush $Y$ standing at different points of $X$, you can remove points of the brush and it will still paint the same region.

One of my favourite examples of this is the Minkowski Sum of two unit circles. They look very 'thin', but when you use one as a brush over the other you will see it is enough to cover a solid disk of radius 2.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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