On the largest convex subsets in Minkowski sums

Abstract

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.

Keywords

• Minkowski sum
• Combinatorics of planar point sets
• Convex subsets
• Combinatorial problems