Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose that the convex hull of the Minkowski sum of several compact connected sets in $\mathbb R^d$ contains the unit ball centered at the origin and the diameter of each set is less than $\delta$. If $\delta$ is very small (this smallness may depend on $d$ but on nothing else), does it follow that the sum itself contains the origin?

share|improve this question
WRONG TAGS --- it should be geometry or/and convex-geometry... –  Anton Petrunin Nov 23 '09 at 1:40
This was asked long before such tags existed and before I would be able to create them. I'm not really sure what are the best tags for this now (I chose these two because the question arose in a purely analytic setting and it seemed topological in nature) but I do not mind in the slightest if somebody more comfortable with the vast forest of the current tags will retag it. I am currently completely lost in the aforementioned forest, so I'll take no action myself. –  fedja Nov 23 '09 at 2:59

4 Answers 4

up vote 12 down vote accepted

I finally figured it out. My solution is here. I would repost it on mathoverflow but until LaTeX is enabled, it is quite hard for me to communicate such things here...

share|improve this answer

In dimension 1, why are the sets {-100}, {80},{120} not a counterexample?

(In particular, they are compact connected sets with 'diameter' 0; their Minkowski sum, going by the wikipedia definition, is {-20,20,200}, which does not contain 0, but whose convex hull [-20,200] contains a large ball around 0)

This example of course has nothing to do with dimension, and you can easily flush out the points into tiny balls, if you like. I suspect that this is based on a misreading of the question.

share|improve this answer
The Minkowski sum of those sets is the set {100}. The Wikipedia article discusses the Minkowski sum of two sets. But this is a commutative and associative operation, so we can discuss the Minkowski sum of any finite number of sets. –  David Speyer Oct 27 '09 at 16:12
As David Speyer points out, the Minkowski sum is a singleton in this case. My only reason for making this comment is to say that I came up with exactly the same "counterexample" myself at one point, and even started writing an answer based on it. But then I realized my mistake. –  gowers Oct 29 '09 at 11:53

Argh! I tried to add this as a comment but when submitting it, I was told that there was a 600 character limit and all my typing just disappeared without trace.

Anyway, my point was that you can get "straight paths". The reason is that if $a=\sum_ i x_ i$ and $b=\sum_ i y_ i$ are in the sum, then the vectors $v_ i=y_ i-x_ i-(b-a)/n$ are small and add up to $0$. There is a cute result that then you can rearrange them in such order that all partial sums are small (just constant times larger than the vectors themselves). If you switch from $x_ i$ to $y_ i$ along the corresponding compact in this order, you get a curve that travels from $a$ to $b$ within a small neighborhood of the segment $[a,b]$.

Another observation that may be useful is that the sum is $d\delta$ dense in its convex hull. Indeed, if $a=\sum_ i v_ i$ and $v_ i$ are in the convex hull of $K_ i$, then we can start moving $v_ i$ until their representations as convex combinations of points in $K_ i$ get shorter and we can do it as long as there are at least $d+1$ vectors $v_ i$ that do not belong to $K_ i$ themselves (any $d+1$ vectors in $\mathbb R^d$ are linearly dependent). Thus, in the representation of every point in the convex hull as a sum, we need only $d$ vectors from convex hulls and the rest may be taken in $K_ i$.

I feel that these two observations put together should be enough and I just do not see how to add 2 and 2 here.

share|improve this answer

I don't have a proof yet, but here are some ideas that might lead to one. I'll stick to two dimensions. Suppose that your sets are X_ 1,X_ 2,...,X_ m and in each X_ i-X_ i you take a vector x_ i. Now let's suppose that x_ 1+...+x_ r=x and x_ {r+1}+...+x_ m=y, and that x and y are quite a lot bigger than the x_ i and point in very different directions. Then the Minkowski sum of the X_i contains a path that goes from some z to z+x and from there to z+x+y, using bits out of different sets for the two parts of the path. Now we could get from z to z+x+y using the same bits in a different order. For exampe we could go first to z+y and from there to z+x+y. And I'm fairly sure that a topological argument will show that the region bounded by those four bits of path will all be in the Minkowski sum. So it would be enough to show that we can get paths that are reasonably straight.

Why should the bits in between be in the Minkowski sum? It's enough to prove that in the case r=1 and m=2. (After that one just keeps swapping xs from the first half with xs from the second half -- I hope all this is making sense, but I haven't thought about it carefully enough to be sure it isn't stupid in some way.) If X_ 1 contains a path P_ 1 from 0 to x (WLOG) and X_ 2 contains a path x+P_ 2 from x to y, and if the four paths P_ 1, x+P_ 2, P_ 2, y+P_ 1 do not cross and bound some region, then the sets P_ 1+u with u in P_ 2 trace out that region I think.

There are plenty of details to check there and even if they all work one still needs to prove that in the Minkowski sum you can get from any point to any other using a "reasonably straight path", whatever that means. So this is just my preliminary thoughts.

A very nice problem, though!

share|improve this answer

Your Answer


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.