Open caps and cups in planar point sets (Q2369923)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Open caps and cups in planar point sets |
scientific article |
Statements
Open caps and cups in planar point sets (English)
0 references
21 June 2007
0 references
Erdős and Szekeres proved their classical result, Theorem 1. For any \(n\geq 3\), there exists a (least) integer \(F(n)\) such that any set of at least \(F(n)\) points in general position in the plane contains \(n\) points in convex position, by showing that for any \(k,\ell\geq 2\) there is a (least) integer \(F'(k,\ell)\) such that any configuration of at least \(F'(k,\ell)\) points contains a \(k\)-cap or an \(\ell\)-cup. Here a configuration \(P\) is a finite set of points in general position in the plane such that no two points have the same \(x\)-coordinate; and a \(k\)-cap (resp. \(k\)-cup) is a sequence of \(k\) points \(p_1,\dots, p_k\) with increasing \(x\)-coordinates that are the vertices of a convex \(k\)-gon with all points \(p_2,\dots, p_{k-1}\) lying above (resp. below) the segment \(p_1p_k\). Here the author investigates the related problem of open caps and cups, i.e. caps and cups with no points of the configuration vertically above, resp. below, the polygonal arc \(p_1,\dots, p_k\). He gives double exponential bounds for the minimal size of \(P\).
0 references
Erdős-Szekeres
0 references
(open) caps and cups
0 references