<p>There must be many ways to do it - here is one way...</p>
<p>Compute the medial axis of the polygon using  the <span class="math-container">$L_1$</span> metric. Any point on the boundary defines a natural segment that goes from this point to a point on the medial axis - lets call the leash of the point. Pick an arbitrary point on the boundary of the polygon, and start moving it counterclockwise. Continue sweeping until the leash sweeps over area <span class="math-container">$1/m$</span> of the polygon. The swept area is a connected polygon of the desired area. Now continue in this fashion breaking the polygon into <span class="math-container">$m$</span> connected polygons of the same area.</p>

CC BY-SA 4.0
2021-02-23T16:59:03.063Z
Very interesting, thanks. Two questions: (a) does this work also when using the straight skeleton instead of the medial axis? (b) Is it correct to say that any partition of the medial axis / straight skeleton into $m$ connected components, induces a unique partition of the polygon into  $m$  connected polygons?
Erel Segal-Halevi
CC BY-SA 4.0
2021-02-23T20:54:58.197Z
(A) I think so but I am not totally sure.
(B) You are really treating each segment of the medial axis as having two sides. So you are really going around the tree (which can be interpreted as a cycle, and partitioning it into m parts), but if you do that, then yes, I believe any such "weighted" partition should work.
Sariel Har-Peled
CC BY-SA 4.0
2021-02-22T16:15:28.713Z
2021-02-22T22:28:45.450Z
2021-02-22T22:28:45.450Z
Sariel Har-Peled
<p>To complement Sariel's answer, some closely related problems are hard. In particular, for a non-convex polygon, it's NP-hard to find a partition into two pieces of equal area while minimizing the length of the cut. See: Elias Koutsoupias, Christos Papadimitriou, and Martha Sideri (1992), &quot;On the optimal bisection of a polygon&quot;, <em>ORSA J. Comput.</em> 4 (4): 435–438, <a href="https://doi.org/10.1287/ijoc.4.4.435" rel="nofollow noreferrer">doi:10.1287/ijoc.4.4.435</a>.</p>

CC BY-SA 4.0
2021-02-24T07:55:15.393Z
2021-02-24T07:55:15.393Z
David Eppstein
<p><a href="https://www.sciencedirect.com/science/article/pii/S0304397515007203" rel="nofollow noreferrer">Armaselu and Daescu (TCS, 2015)</a> present algorithms that, given a convex polygon <span class="math-container">$P$</span> and an integer <span class="math-container">$m$</span> (which  must be a power of <span class="math-container">$2$</span>), return a partition of <span class="math-container">$P$</span> into <span class="math-container">$m$</span> convex polygons with the same area and same perimeter.</p>
<p>If we only want the area to be equal (and do not care about perimeter), then the problem becomes easy for any <span class="math-container">$m$</span>: move a &quot;knife&quot; (a straight line) over <span class="math-container">$P$</span> from left to right, and make a cut whenever the area covered by the knife is <span class="math-container">$1/m$</span>. Since <span class="math-container">$P$</span> is convex, the resulting pieces are convex too.</p>
<p>But what if <span class="math-container">$P$</span> is not convex? Then, cutting <span class="math-container">$P$</span> by a knife might generate pieces that are not convex and even not connected.</p>
<p>What is an algorithm for partitioning a polygon (that is connected but not necessarily convex) into <span class="math-container">$m$</span> connected polygons?</p>
<p>My guess is that the problem should be much easier for hole-free polygons. But even for this case, I could not find an algorithm.</p>

CC BY-SA 4.0
2021-02-22T19:37:07.770Z
What's wrong with triangulating the polygon (based on the boundary points) and then let say start from the rightmost boundary triangle, and if it is smaller than 1/m, add a (edge) neighboring triangle to it and repeat, until the area of union of these triangles is at least 1/m. At that point, from the last triangle take the desired portion and attach it to previous triangles and output it as the first piece, repeat this process for the rest of m-1 remaining pieces in the remaining polygon.
Saeed
CC BY-SA 4.0
2021-02-22T22:30:54.097Z
A triangle might connect three different parts of the polygons. If you add it to your portion, you make the complement region disconnected...
Sariel Har-Peled
CC BY-SA 4.0
2021-02-23T09:54:48.957Z
That's a good point, but I think it is possible to resolve this issue: find all such triangles (cut triangles) then make one vertex for each of them and put weights on these vertices w.r.t. their area, then remove them and for each of the remaining connected components make one vertex with corresponding weight. Connect two vertices if they had a common edge in the polygon. We can root this tree and find the lowest cut vertex, then analyze based on the weight of its left and right branches. I may later write an answer based on this argument (if nothing is missing).
Saeed
CC BY-SA 4.0
2021-02-28T20:25:26.887Z
I am not against such an approach - it is just that these things might require a long sequence of fixes before you get to a final answer that works. You need a "trick" to make the polygons connected (in my answer I used the outer boundary to "hang" the polygons so that they are connected).
Sariel Har-Peled
<cg.comp-geom><partition-problem><polygon>
Partitioning a connected polygon into connected pieces of equal area
Erel Segal-Halevi
# Partitioning a connected polygon into connected pieces of equal area

(Asked by: username_0 on 2021-02-22)

[Armaselu and Daescu (TCS, 2015)](https://www.sciencedirect.com/science/article/pii/S0304397515007203) present algorithms that, given a convex polygon $P$ and an integer $m$ (which must be a power of $2$), return a partition of $P$ into $m$ convex polygons with the same area and same perimeter.

If we only want the area to be equal (and do not care about perimeter), then the problem becomes easy for any $m$: move a "knife" (a straight line) over $P$ from left to right, and make a cut whenever the area covered by the knife is $1/m$. Since $P$ is convex, the resulting pieces are convex too.

But what if $P$ is not convex? Then, cutting $P$ by a knife might generate pieces that are not convex and even not connected.

What is an algorithm for partitioning a polygon (that is connected but not necessarily convex) into $m$ connected polygons?

My guess is that the problem should be much easier for hole-free polygons. But even for this case, I could not find an algorithm.

**Tags:** cg.comp-geom, partition-problem, polygon
> **Comments:**
> **username_1**: What's wrong with triangulating the polygon (based on the boundary points) and then let say start from the rightmost boundary triangle, and if it is smaller than 1/m, add a (edge) neighboring triangle to it and repeat, until the area of union of these triangles is at least 1/m. At that point, from the last triangle take the desired portion and attach it to previous triangles and output it as the first piece, repeat this process for the rest of m-1 remaining pieces in the remaining polygon.  
> **username_2**: A triangle might connect three different parts of the polygons. If you add it to your portion, you make the complement region disconnected...  
> **username_1**: That's a good point, but I think it is possible to resolve this issue: find all such triangles (cut triangles) then make one vertex for each of them and put weights on these vertices w.r.t. their area, then remove them and for each of the remaining connected components make one vertex with corresponding weight. Connect two vertices if they had a common edge in the polygon. We can root this tree and find the lowest cut vertex, then analyze based on the weight of its left and right branches. I may later write an answer based on this argument (if nothing is missing).  
> **username_2**: I am not against such an approach - it is just that these things might require a long sequence of fixes before you get to a final answer that works. You need a "trick" to make the polygons connected (in my answer I used the outer boundary to "hang" the polygons so that they are connected).  

---

## 2 answers

### Answer by username_2 on 2021-02-22. Score: 3 | Accepted answer

There must be many ways to do it - here is one way...

Compute the medial axis of the polygon using the $L\_1$ metric. Any point on the boundary defines a natural segment that goes from this point to a point on the medial axis - lets call the leash of the point. Pick an arbitrary point on the boundary of the polygon, and start moving it counterclockwise. Continue sweeping until the leash sweeps over area $1/m$ of the polygon. The swept area is a connected polygon of the desired area. Now continue in this fashion breaking the polygon into $m$ connected polygons of the same area.

> **Comments:**
> **username_0**: Very interesting, thanks. Two questions: (a) does this work also when using the straight skeleton instead of the medial axis? (b) Is it correct to say that any partition of the medial axis / straight skeleton into $m$ connected components, induces a unique partition of the polygon into  $m$  connected polygons?  
> **username_2**: (A) I think so but I am not totally sure. (B) You are really treating each segment of the medial axis as having two sides. So you are really going around the tree (which can be interpreted as a cycle, and partitioning it into m parts), but if you do that, then yes, I believe any such "weighted" partition should work.  

---

### Answer by username_3 on 2021-02-24. Score: 4

To complement Sariel's answer, some closely related problems are hard. In particular, for a non-convex polygon, it's NP-hard to find a partition into two pieces of equal area while minimizing the length of the cut. See: Elias Koutsoupias, Christos Papadimitriou, and Martha Sideri (1992), "On the optimal bisection of a polygon", *ORSA J. Comput.* 4 (4): 435–438, [doi:10.1287/ijoc.4.4.435](https://doi.org/10.1287/ijoc.4.4.435).


---

