On polygons enclosing point sets (Q2752520)

The authors consider point sets \(V\) and \(W\) in the plane in general position with cardinality \(n\) and \(m\) respectively and give the following definition: A subset \(S\) of \(W\) is enclosed by \(V\) if there is a simple polygon \(P\) with vertex set \(V\) such that all the points of \(S\) are interior to \(P\). Following the tradition of computing optimal polygonizations according to some criterion they prove that if \(W\) is contained in the interior of the convex hull of \(V\), then \(V\) encloses at least half of the points of \(W\). They also prove that if the convex hull of \(V\) has at least \(\min \{ 56m, (2 \lceil \log m \rceil + 1) m \}\) vertices, then \(V\) encloses the whole of \(W\).