On the existence of a convex point subset containing one triangle in the plane (Q2581413)

The paper refers to planar point sets \(P\) in general position, i.e., no three points of \(P\) are collinear. For a subset \(S\) whose convex hull ch\((S)\) contains no points from \(P\setminus S\) one distinguishes the vertices (lying on the boundary of ch\((S)\)) from the remaining interior points of \(S\). A convex region \(D\) is called empty if no interior points of \(P\) belong to the interior of \(D\). A well-known theorem of \textit{P. Erdős} and \textit{G. Szekeres} [Compos. Math. 2, 463--470 (1935; Zbl 0012.27010)] asserts that for every integer \(t\geq 3\) there is a number \(f(t)\) such that every set \(P\) of cardinality at least \(f(t)\) contains a subset with precisely \(t\) vertices. \textit{J. Horton} [Can. Math. Bull. 26, 482--484 (1983; Zbl 0521.52010)] proved that one cannot in general control simultaneously the number of vertices and the number of interior points. \textit{D. Avis, K. Hosono} and \textit{M. Urabe} [Discrete Math. 241, 33--40 (2001; Zbl 1087.52505)] have considered point sets in which there is a convex set with a prescribed number of interior points. For \(k\geq 1\), let \(g(k)\) be the smallest integer such that every planar set containing at least \(g(k)\) interior points has a convex subset containing exactly \(k\) interior points. The only values for which the existence of \(g(k)\) is proved are \(k=1,2\). The best lower bound for \(g(k)\) presently published is due to \textit{T. Fevens} [Lect. Notes Comput. Sci. 2866, 152--158 (2003)]. The main result of the paper under review is that \(g(3)= 8\) provided that one only considers point sets without empty convex hexagons. The proof is by induction on the number of interior points. The most difficult case is when ch\((P)\) is a triangle with 8 interior points. The author conjectures that \(g(3)\) is finite.