Planar sets with few empty convex polygons (Q2714367)

Let \(g_i(n)\) be the minimum number of empty convex polygons with \(i\) vertices that is necessarily contained in any collection of \(n\) points in the plane, no three of them on a straight line (call this a generic collection of \(n\) points). For example \(g_4(n) \geq k\) means that any such collection of \(n\) points always contains at least \(k\) empty convex quadrilaterals. It has been known by a construction of Horton that \(g_i(n) = 0\) for \(i\geq 7\). For \(i\leq 5\) upper and lower bounds for \(g_i(n)\) are known and for \(g_6(n)\) only an upper bound is known, so that it is still an open problem whether any generic collection of \(n\) points contains an empty convex hexagon. In this paper improved upper bounds are given for \(g_i(n)\) for \(i=3,4,5,6\), as far as the multiplicative constants are concerned: \(g_3(n) \leq 1.683 n^2,\;g_4(n) \leq 2.132 n^2,\;g_5(n) \leq 1.228 n^2,\;g_6(n) \leq 0.297 n^2\).