Convexly Independent Subsets of the Minkowski Sum of Planar Point Sets

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

Abstract

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)$.

Published
2008-03-20
Article Number
N8