Abstrakt
Given two point sets A, B in the plane of n points each, the Minkowski sum A + B has a quadratic number of points in general. How large can a subset S of A + B be if S is required to be convex? We prove that when A and B are both convex then S can have only O ( n log n ) points.
This complements the existing results that are known when A and B are not in convex position or when B = A and A is convex.