A Tight Lower Bound for Convexly Independent Subsets of the Minkowski Sums of Planar Point Sets

  • Ondřej Bílka
  • Kevin Buchin
  • Radoslav Fulek
  • Masashi Kiyomi
  • Yoshio Okamoto
  • Shin-ichi Tanigawa
  • Csaba D. Tóth

Abstract

Recently, Eisenbrand, Pach, Rothvoß, and Sopher studied the function $M(m, n)$, which is the largest cardinality of a convexly independent subset of the Minkowski sum of some planar point sets $P$ and $Q$ with $|P| = m$ and $|Q| = n$. They proved that $M(m,n)=O(m^{2/3}n^{2/3}+m+n)$, and asked whether a superlinear lower bound exists for $M(n,n)$. In this note, we show that their upper bound is the best possible apart from constant factors.

Published
2010-10-29
Article Number
N35