2
$\begingroup$

Armaselu and Daescu (TCS, 2015) 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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Saeed
    Feb 22, 2021 at 19:37
  • 2
    $\begingroup$ A triangle might connect three different parts of the polygons. If you add it to your portion, you make the complement region disconnected... $\endgroup$
    – Sariel Har-Peled
    Feb 22, 2021 at 22:30
  • $\begingroup$ 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). $\endgroup$
    – Saeed
    Feb 23, 2021 at 9:54
  • $\begingroup$ 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). $\endgroup$
    – Sariel Har-Peled
    Feb 28, 2021 at 20:25

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Erel Segal-Halevi
    Feb 23, 2021 at 16:59
  • $\begingroup$ (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. $\endgroup$
    – Sariel Har-Peled
    Feb 23, 2021 at 20:54
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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