On the minimum number of mutually disjoint holes in planar point sets
Let us be given a set \(P\) of \(n\) points in general position in the Euclidean plane. Some \(k\) points of \(P\) make a \(k\)-hole, if they determine a convex \(k\)-gon, not containing any more points from \(P\). Let \(g(P)\) denote the minimum number of holes into which \(P\) can be partitioned, and let \(f(P)\) denote minimum number of holes into which \(P\) can be partitioned such that the convex hulls of the holes are pairwise disjoint. Furthermore, let \(G(n)\) be the maximum of \(g(P)\) for \(|P|=n\), and let \(F(n)\) be the maximum of \(f(P)\) for \(|P|=n\). \textit{M. Urabe} [Discrete Appl. Math. 64, No. 2, 179--191 (1996; Zbl 0849.52015)] started the investigation of these quantities. The paper under review shows \(\lfloor n/4 \rfloor +1\leq G(n)\leq F(n) \leq \lceil n/4\rceil +1\). Even if they are close, these functions are not equal as \(G(11)<F(11)\).
scientific article; zbMATH DE number 6531079
scientific article