On the minimum size of a point set containing a 5-hole and double disjoint 3-holes (Q745644)

Given a finite planar set \(P\) in general position, i. e. no three points in \(P\) are collinear, then a subset of \(k\) points of \(P\) is said to form a \(k\)-hole of \(P\) if these \(k\) points are vertices of a convex polygon whose interior contains no points of \(P.\) The problem of determining minimum cardinality of \(P\) that guarantees the existence of a \(k\) hole or multiple disjoint holes in any finite point set of equal or greater cardinality has an interesting tradition. In 1978 Paul Erdős posed a problem to determine if for every \(k\) there exists the smallest integer \(n(k)\) such that any set of planar points in general position with at least \(n(k)\) points would contain a \(k\)-hole [\textit{P. Erdős}, Aust. Math. Soc. Gaz. 5, 52--54 (1978; Zbl 0417.52002)]. It is easy to verify that \(n(3) = 3, \; n(4) = 5,\) and it was proved that integers \(n(k)\) exist for \(k < 7\). However, \textit{J. D. Horton} proved that \(n(k)\) does not exist for \(k \geq 7\) [Can. Math. Bull. 26, 482--484 (1983; Zbl 0521.52010)]. Further developments led to the study of existence of the number \(n(p, q), \; p \leq q,\) defined as the smallest positive integer (if it exists) such that any planar set of at least \(n(p, q)\) points in general position contains a \(p\)-hole and a \(q\)-hole which are mutually disjoint, i.e. the convex hulls of the corresponding points that are vertices of these polygonal holes are disjoint. \textit{K. Hosono} and \textit{M. Urabe} computed the exact values for \(n(2, 4) = 6\), \(n(3, 3) = 6\), \(n(3, 4) = 7\), \(n(3, 5) = 10\), \(n(4, 4) = 9\) and gave bounds for \(n(p, q)\) for some higher values of \(p\) and \(q\) (see e. g. [Lect. Notes Comput. Sci. 4535, 90--100 (2008; Zbl 1162.52302)]). Next level of generalization led to the study of existence of the smallest positive integer \(n (k, l, m)\) as depending on given integers \(k \leq l \leq m\), defined by the property that any planar set of at least \(n(k, l, m)\) points in general position contains a \(k\)-hole, an \(l\)-hole and an \(m\)-hole which are mutually disjoint. One of the earlier results of Hobson and Urabe is that \(n(2, 3, 5) = 11\). In the paper under review the authors make further advance in the theory by proving that \(n(3, 3, 5) = 12\), which is the main result of this paper.