2
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\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.

$\endgroup$
3
  • $\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, 2022 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, 2022 at 19:22
  • $\begingroup$ @sn3jd3r, if this answer answers your question, would you mind marking it as accepted? $\endgroup$
    – Neal Young
    Nov 4, 2022 at 1:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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