3
$\begingroup$

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

3 Answers 3

12

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

  • 0
    @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.2011-10-09
4

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

  • 4
    But $Y$ is convex.2011-10-09
0

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.