scientific article; zbMATH DE number 2068096
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].
- A sufficient condition for the existence of large empty convex polygons
- A modular version of the Erdős– Szekeres theorem
- A Remark on the Erdos-Szekeres Theorem
- On weighted sums of numbers of convex polygons in point sets
- A note on point subset with a disjoint triple of two 4-holes and a 5-hole
- The empty hexagon theorem
- Holes or empty pseudo-triangles in planar point sets
- A note on the number of empty triangles
- Problems and results around the Erdős-Szekeres convex polygon theorem
- On empty triangles determined by points in the plane
- A new proof of the Erdős-Szekeres convex k-gon result
- Erdős--Szekeres theorem with forbidden order types
- Erdős problems on irregularities of line sizes and point degrees
- The Erdos-Szekeres problem on points in convex position – a survey
- Erdős-Szekeres theorem for point sets with forbidden subconfigurations
- Initial sequences and Waldschmidt constants of planar point configurations
- No repeated slopes, triangles and polygons
- A Remark on the Erdos-Szekeres Theorem
- Two player game variant of the Erdős-Szekeres problem
- On Erdős-Szekeres-type problems for \(k\)-convex point sets
- On Erdős-Szekeres-type problems for \(k\)-convex point sets
- An Erdős-Szekeres type problem in the plane
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)