So, this is the promised actual first post, motivated by and answering a question recently posed to me by Yue Ren (and several before him that I apologize for forgetting). It comes with a problem, and that is, to prove the result in a simpler, more elementary way.

I had written a longer paper (with Raman Sanyal) on a problem concerning Upper Bounds on the complexity of Minkowski sums that dealt with the problem quite thoroughly.

But after we submitted the paper, and it was accepted and published in Publications IHES, someone asked me a question. I thought for a while, and answered that it follows from that and that lemma in the paper. But the question came up again and again, seemingly being quite relevant. On the other hand, writing a new paper on the matter was tedious, as it promised to be 90% repetition of paper number one. Which was an annoying prospect at best.

The problem is this: Consider a bunch (say m of polytopes in a euclidean vector space of dimension d. For simplicity, and to be interesting, let us assume that all these polytopes are of positive dimension. Also, let us assume that all these polytopes are in general position with respect to each other.

Question: How many vertices must the Minkowski sum of the family have? Surely, it has to be at least the number of vertices as the Minkowski sum of m segments in general position.

Continue reading →