A simple proof for open cups and caps

Let XX be a set of points in general position in the plane. General position means that no three points lie on a line and no two points have the same xx-coordinate. Y⊆XY⊆X is a cup (resp. cap  ) if the points of YY lie on the graph of a convex (resp. concave) function. Denote the points of YY by p1,p2,…,pmp1,p2,…,pm according to the increasing xx-coordinate. The set YY is open   in XX if there is no point of XX above the polygonal line p1,p2,…,pmp1,p2,…,pm. Valtr [P. Valtr, Open caps and cups in planar point sets, DCG (in press)] showed that for every two positive integers kk and ll there exists a positive integer g(k,l)g(k,l) such that any g(k,l)g(k,l)-point set in the plane in general position contains an open kk-cup or an open ll-cap. This is a generalization of the Erdős–Szekeres theorem on cups and caps. We show a simple proof for this theorem and we also show better recurrences for g(k,l)g(k,l). This theorem implies results on empty polygons in k′k′-convex sets proved by Károlyi et al. [Gy. Károlyi, J. Pach, G. Tóth, A modular version of the Erdős–Szekeres theorem, Studia Sci. Math. Hungar. 38 (2001) 245–259], Kun and Lippner [G. Kun, G. Lippner, Large convex empty polygons in kk-convex sets, Period. Math. Hungar. 46 (2003) 81–88] and Valtr [P. Valtr, A sufficient condition for the existence of large empty convex polygons, Discrete Comput. Geom. 28 (2002) 671–682; P. Valtr, Open caps and cups in planar point sets, DCG (in press)]. A set of points is k′k′-convex if it determines no triangle with more than k′k′ points inside.