scientific article; zbMATH DE number 2068096

From MaRDI portal
Publication:4464707





The classical Erdős-Szekeres convex polygon theorem states that for each \(k\) there is an \(n(k)\) such that any set of \(n(k)\) points in the plane, no three of them on a line, contains \(k\) points that are vertices of a convex \(k\)-gon. This theorem has been generalized in many directions. In this paper, the authors begin by relaxing the `no three points collinear' assumption to `no \(l\) points collinear' or equivalently the convex hull of any two points contains at most \(l\) points. The condition on the admissible sets can then be made stronger again as `the convex hull of any \(k\) points contains at most \(l\) points of the sets. For each \(k,l\) the authors give bounds for the analogue of the Erdős-Szekeres theorem, the minimum number \(f^n_{(k,l)}\) such that any set of \(f^n_{(k,l)}\) points, in which the convex hull of any \(k\) points contains at most \(l\) points, contains the vertices of a convex \(n\)-gon. Sets with a similar restriction with \(k=3\) (each triangle contains at most \(l\) points) have already been studied in the context of the `empty polygon'-variant by \textit{P. Valtr} [Discrete Comput. Geom. 28, No. 4, 671--682 (2002; Zbl 1022.52007)]. For the entire collection see [Zbl 1034.52002].











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4464707)