# Optimal solution for partitioning convex polygon

Given a convex polygon $$P$$ (possibly) with holes. We want to partition $$P$$ into a minimum number of connected interior-disjoint polygons $$P_1,...P_s$$. The definition of restriction on the pieces is that each polygons $$P_i$$ is contained in a unit circle. The corners of the polygon can lie anywhere in $$P$$ or its boundary.

Conjecture : For a convex polygon $$P$$ with holes as described above there exists an optimal solution where polygons $$P_1,...,P_k$$ that do not share a boundary with a hole are convex.

I am aware that for simple polygons with holes, and without Steiner points the problem is NP-hard. If anyone knows of other results similar to my conjecture or can see a simple proof I would be happy.

Proof idea : Consider a convex polygon without holes. An optimal solution exists that consists of convex polygons $$P_1,...P_s$$. Assume a piece $$P_j$$ is not convex, since $$P$$ is convex you cannot lose anything by making $$P_j$$ convex. Now add the holes. Only polygons that share a boundary with the holes are not convex any more. Issue: Is it possible that an optimal solution differs by adding the holes after rather than before?

Edit: Seeing the counterexample by Wei I would be happy with the small pieces being weakly simple i.e such that the polygons containing C and D can touch the boundary of the hole in which case the piece containing A,B would not have connected interior, but would be connected via a segment.

• Thank you. Seeing this I think I would be happy with the small pieces being weakly simple i.e such that the pieces containing $C$ and $D$ can touch the boundary of the hole in which case the piece containing $A,B$ would not have connected interior, but would be connected in the sense that the piece would degenerate and share a boundary with both the hole and the pieces containing $C$ and $D$. As far as I can tell this would not serve as a counterexample in such a case. I will upvote it for now, and accept it in bit if no one chimes in after this relaxation. Feb 27, 2022 at 18:53