2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Counterexample Here's an counterexample when each piece is contained in a unit circle. For any solution with at most 3 pieces, A and B must be in the same piece (otherwise A,B,C,D are all in different pieces), which forms exactly a diameter. So the pieces that contain C and D must include the greyish area and cannot be convex. But when they both touch the hole, A and B are not connected anymore.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – sn3jd3r
    Feb 27 at 18:53
  • $\begingroup$ @sn3jd3r Well then I think your conjecture is true. Changing any non-convex piece that doesn't touch any hole into the intersection of its convex hull and the polygon, will make it either convex or make it touch the hole. In the latter case the connectivity of other pieces are not affected because the boundary of the hole works as paths, so I guess still nothing is lost. $\endgroup$
    – Wei Zhan
    Feb 27 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.