Charles Explorer logo
🇬🇧

Open caps and cups in planar point sets

Publication at Faculty of Mathematics and Physics |
2007

Abstract

We prove the following generalization of the Erd\H{o}s-Szekeres theorem. For any $k$, any sufficiently large set $P$ of points in general position contains $k$ points, $p_1,p_2,\dots,p_k$, that form either a $k$-cap or a $k$-cup, and there is no point of $P$ vertically above the polygonal line $p_1p_2\dots p_k$.