Given a convex polygon $P$ (possibly) with holes. We want to partition $P$ into a minimum number of connected interior-disjoint small pieces $Q_1,...Q_s$. The definition of small can either be that each piece $Q_i$ is contained in a unit square or a unit circle (I am fine with a proof that shows my conjecture for either definition). We allow Steiner points in our solution
Conjecture : For a convex polygon $P$ with holes as described above there exists an optimal solution where pieces the $Q_1,...,Q_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 see e.g. this paper. There are also a few papers looking at simply polygons without holes (see here). 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 small pieces $Q_1,...Q_s$. Assume a piece $Q_j$ is not convex, since $P$ is convex you cannot lose anything by making $Q_j$ convex. Now add the holes. Only pieces 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 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.