Forcing empty convex polygons

Let us call a convex polygon \( P\) formed from the points of a set \( X\) empty if the interior of \( P\) contains no point of \( X\). Erdös suggested the following variation.

For each \( n\), let \( g^*(n)\) denote the least integer such that any set of \( g^*(n)\) points in the plane in general position must always contain the vertices of an empty convex \( n\)-gon. This is a slight variation of \( g(n)\) of Erdös and Szekeres.

Problem

Is it true that \(g^*(n)\) always exists, and if it does, determine or estimate \(g^*(n)\).

It is easy to show that \( g^*(3)=3\) and \( g^*(4)=5\).

Harborth [4] showed that \( g^*(5)=10\).

Horton [5] constructed an infinite set of points with no empty convex 7-gon, implying that \( g^*(7)= \infty\).

Overmars [8] used a computer to find a set of 29 points without an empty convex hexagon. This proved \( g^*(6) \ge 30\).

Gerken [3] proved that \( g^*(6)\) is finite. By case analysis, he showed that any set with a convex 9-gon must contain an empty hexagon. Using the function \( g(n)\) from the Erdös Szekeres theorem, this means that \( g^*(6) \le g(9)\), which is known to be between 129 and 1717. Nicolas [7] independently proved that \( g^*(6)\) is finite, bounding it by \( g(25)\).

Koshelev [6] further showed that \( g^*(6) \le \max\{g(8), 400\}\), which gives the current upper bound of 463.

A weaker restriction in this vein has been considered by Bialostocki, Dierker and Voxman [1]. They prove that there is a function \( E(n,q)\) such that if \( X\) is a subset of the plane in general position with \( \vert X\vert \geq E(n,q)\), then \( X\) always contains the vertices of a convex \( n\)-gon with \( tq\) points of \( X\) in its interior for some integer \( t\), where \( n \geq q+2\). Caro [2] shows that one can always take \( E(n,q) \leq 2^{c(q)n} \) where \( c(q)\) depends only on \( q\).


Bibliography
1 A. Bialostocki, P. Dierker and W. Voxman, Some notes on the Erdös-Szekeres theorem, Discrete Math. 91 (1991), 117-127.

2 Y. Caro, On the generalized Erdös-Szekeres Conjecture- a new upper bound, Discrete Math. 160 (1996), 229-233.

3 T. Gerken, ``On empty convex hexagons in planar point set,'' Discrete Comput. Geom., 39, 239–272 (2008).

4 H. Harborth, Konvexe Fünfecke in ebenen Punktmengen, Elem. Math. 33 (1978), 116-118.

5 J. D. Horton, Sets with no empty convex \( 7\)-gons, Canad. Math. Bull. 26, (1983), 482-484.

6 V. A. Koshelev, ``On the Erdös-Szekeres problem,'' Doklady Mathematics, 76, No. 1, 603-605 (2007)

7 C. Nicolas, ``The empty hexagon theorem,'' Discrete Comput. Geom., 38, No. 2, 389–397 (2007).

8 M. Overmars, ``Finding sets of points without empty convex 6-gons,'' Discrete Comput. Geom., 29, 153–158 (2003).