Convexly Independent Subsets of the Minkowski Sum of Planar Point Sets

Friedrich Eisenbrand, János Pach, Thomas Rothvoß, Nir B. Sopher


Let $P$ and $Q$ be finite sets of points in the plane. In this note we consider the largest cardinality of a subset of the Minkowski sum $S\subseteq P \oplus Q$ which consist of convexly independent points. We show that, if $|P| = m$ and $|Q| = n$ then $|S| = O(m^{2/3} n^{2/3} + m + n)$.

Full Text: PDF