<p><a href="https://i.sstatic.net/5v23O.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/5v23O.png" alt="Counterexample" /></a>
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.</p>

CC BY-SA 4.0
2022-02-27T18:53:18.507Z
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.
sn3jd3r
CC BY-SA 4.0
2022-02-27T19:22:18.047Z
@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.
Wei Zhan
CC BY-SA 4.0
2022-11-04T01:14:03.730Z
@sn3jd3r, if this answer answers your question, would you mind marking it as accepted?
Neal Young
CC BY-SA 4.0
2022-02-27T18:14:45.077Z
2022-02-27T18:30:29.610Z
2022-02-27T18:30:29.610Z
Wei Zhan
<p>Given a convex polygon <span class="math-container">$P$</span> (possibly) with holes. We want to partition <span class="math-container">$P$</span> into a minimum number of connected interior-disjoint polygons <span class="math-container">$P_1,...P_s$</span>. The definition of restriction on the pieces is that each polygons <span class="math-container">$P_i$</span> is contained in a unit circle. The corners of the polygon can lie anywhere in <span class="math-container">$P$</span> or its boundary.</p>
<p><strong>Conjecture :</strong> For a convex polygon <span class="math-container">$P$</span> with holes as described above there exists an optimal solution where polygons <span class="math-container">$P_1,...,P_k$</span> that do <strong>not</strong> share a boundary with a hole are convex.</p>
<p>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.</p>
<p><strong>Proof idea :</strong> Consider a convex polygon without holes. An optimal solution exists that consists of convex polygons <span class="math-container">$P_1,...P_s$</span>.  Assume a piece <span class="math-container">$P_j$</span> is not convex, since <span class="math-container">$P$</span> is convex you cannot lose anything by making <span class="math-container">$P_j$</span> 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?</p>
<p><strong>Edit:</strong> 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.</p>

<np-hardness>
Optimal solution for partitioning convex polygon
sn3jd3r
# Optimal solution for partitioning convex polygon

(Asked by: username_0 on 2022-02-25)

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.

**Tags:** np-hardness


---

## 1 answers

### Answer by username_1 on 2022-02-27. Score: 2 | Accepted answer

[![Counterexample](https://i.sstatic.net/5v23O.png)](https://i.sstatic.net/5v23O.png)
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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: @username_0 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.  
> **username_2**: @username_0, if this answer answers your question, would you mind marking it as accepted?  

---

