On polygons enclosing point sets. II (Q1043822)

Let \(B\) be a finite point set in the plane (with its points in general position) such that the number of vertices of the polygon Conv\((B)\) is precisely \(k\) and such that there are precisely \(i\) elements of \(B\) in the interior of Conv\((B)\). Let \(n=i+k\). Let \(R\) be another point set in the plane such that \(R\cap B=\emptyset\), \(R\cup B\) is in general position; it is also assumed that all the elements of \(R\) belong to the interior of Conv\((B)\). The authors prove that if \(R\) has at most \(k-1\) points, then there exists a simple polygon \(P\) with vertex set \(B\) such that all the elements in \(R\) belong to the interior of \(P\). They also prove that this bound is tight. This result improves a previous one obtained in part I of this paper [Geombinatorics 11, No.~1, 21--28 (2001; Zbl 1004.52001)]. The main tool used in the proof is the following partitioning lemma which is also very interesting on its own: Let \(P\) be a convex polygon with \(n\) vertices, and \(S\) a point set contained in \(P\) with at most \(n-1\) elements; then there is a set of \(n\) convex polygons \(P_1,\dots,P_n\) with disjoint interiors such that the elements of \(S\) belong to the boundaries of \(P_1,\dots,P_n\) with each \(P_i\) containing on its boundary exactly one edge of \(P\), and satisfying \(P=P_1\cup \dots \cup P_n\).