Interior points in the Erdős-Szekeres theorems
The author investigates the following generalization of the famous Erdős-Szekeres problem. Let \(n\geq 3\) and \(k\geq 0\) be integers. What is the minimal positive integer \(h(n,k)\) with the property that every planar point set of cardinality at least \(h(n,k)\), whose elements are in general position, contains the vertices of a convex \(n\)-gon that has at most \(k\) other points of the set in its interior? In particular, if \(k\geq n-k\), then \(g(n)=h(n,k)\) is the minimal number such that any set of points of cardinality at least \(g(n)\) in the plane in general position contains the vertices of a convex \(n\)-gon; finding \(g(n)\) is the subject of the original Erdős-Szekeres problem. The case \(k=0\) corresponds to another version of the Erdős-Szekeres problem which seeks the minimum number \(h(n)=h(n,0)\) with the property that from any planar point set of cardinality at least \(h(n)\) in general position one can always select the vertices of an empty convex \(n\)-gon. It was proved by Horton in 1983 that \(h(n)\) does not exist for \(n\geq 7\). For \(n\geq 7\), let \(\underline{k}(n)\) be the largest integer for which \(h(n,k)\) does not exist. From the definition it follows that \(g(n)\leq h(n,k)\) for all \(k\geq 0\) and \(h(n,k)\) is a decreasing function of \(k\) (when \(h(k,n)\) exists). Let \(\overline{k}(n)\) denote the integer (if such a number exists) with the propeties that \(h(n, \overline{k}(n)) > g(n)\) and \(h(n,k)=g(n)\) for \(k > \overline{k}(n)\). The main results of the paper include a signifcantly improved lower estimate of \(\underline{k}(n)\) and upper estimates related to \(\overline{k}(n)\).
- Almost empty polygons
- Computer solution to the 17-point Erdős-Szekeres problem
- Finding sets of points without empty convex 6-gons
- scientific article; zbMATH DE number 999569 (Why is no real title available?)
- scientific article; zbMATH DE number 5019923 (Why is no real title available?)
- scientific article; zbMATH DE number 3019031 (Why is no real title available?)
- Konvexe Fünfecke in ebenen Punktmengen
- Sets with No Empty Convex 7-Gons
- The Erdos-Szekeres problem on points in convex position – a survey
- More on an Erdős-Szekeres-type problem for interior points
- Drawing the Horton set in an integer grid of minimum size
- On the Erdös-Szekeres problem
- On the Erdős-Szekeres \(n\)-interior-point problem
- On the computational complexity of Erdős-Szekeres and related problems in \(\mathbb{R}^{3}\)
- On the Erdős-Szekeres n-interior point problem
- scientific article; zbMATH DE number 6169011 (Why is no real title available?)
- A Remark on the Erdos-Szekeres Theorem
- An Erdős-Szekeres type problem in the plane
- Around Erdős-Szekeres problems
- On the minimum size of a point set containing a 5-hole and double disjoint 3-holes
This page was built for publication: Interior points in the Erdős-Szekeres theorems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2435979)
