Large empty convex polygons in \(k\)-convex sets (Q1410439): Difference between revisions

The paper deals with conditions that guarantee the existence of an empty convex \(n\)-gon in any \(k\)-convex point set \(P\). Let \(N_k(n)\) be the smallest number \(N\) in the following theorem. Theorem 1. For arbitrary integers \(k\geq 0\) and \(n\geq 3\) there exists a number \(N\) such that any \(k\)-convex set of at least \(N\) points in general position in the plane contains the vertices of an empty convex \(n\)-gon. The authors prove the following theorems. Theorem 2. If \(P\) is \(k\)-convex and \(|P|\geq (k+2)^{(k+2)^n-1}\), then for any point \(X\) on the convex hull of \(P\) there exists an empty convex \(n\)-gon in \(P\) containing \(X\) as its vertex. Consequently, we have \(N_k(n)\leq (k+2)^{(k+2)^n-1}\leq 2^{(k+2)^{n+1}}\). Theorem 3. \(N_1(n)\leq 2^{\lceil(2n+5)/3\rceil}-1\).