# Partition of polygons into 'congruent sets of polygons'

Definition: Two finite sets of polygons $$A$$ and $$B$$ are congruent if we can match polygons in $$A$$ in a one-one manner with polygons in $$B$$ with each matched pair of polygons mutually congruent.

Question: For every integer $$n$$, can every polygon be partitioned into $$n$$ sets of polygons such that the sets are congruent to one another?

Remarks: For $$n =2$$, the answer is yes. Indeed, one triangulates the input $$m$$-gon, then cuts each triangle into 3 kite polygons (https://en.wikipedia.org/wiki/Kite_(geometry)) that meet at a common vertex at the incenter of the triangle, thus resulting in a total of $$\sim 3m$$ kites. Then we cut each kite into 2 mutually congruent triangles and send each triangle into one of the output sets. This approach results in 2 congruent sets of polygons (indeed, triangles) with $$\sim 3m$$ elements each. For $$n=4$$, one can take the $$n=2$$ solution and divide each triangle piece in each set via kites into 2 congruent sets of 3 triangles each thus resulting in 4 mutually congruent sets with $$\sim 9m$$ triangles each. This approach should work for all powers of 2 values of $$n$$. A natural question here is whether we can manage with less number of pieces in each congruent set.

Guess: For other values of $$n$$, including even 3, the answer may be "not always". I have no proof for this.

• For $n=3$, can't you simply do half of the $n=4$ solution, choose one of the two triangle pieces from the $n=2$ solution and divide it appropriately among the other two sets? Commented Nov 6, 2021 at 19:19
• Pls see answer below. Commented Nov 7, 2021 at 9:37

By the Wallace-Bolyai-Gerwien theorem it suffices to cut the polygon into $$n$$ sets of equal area, which can certainly be done by continuity of the area on one side of a line as you move the line across the shape. If any of the sets is discontiguous you can rearrange pieces to make it contiguous. Then apply WBG to rearrange each set into the shape of an arbitrarily chosen one. Finally, take the union of the cuts on each rearranged set and apply the same cuts to all of them.

Every $$n$$ is possible.

As you point out, it suffices to answer the question for triangles. You can divide a triangle $$T$$ into $$n^2$$ congruent triangles similar to $$T.$$ Then these can be partitioned into $$n$$ sets of $$n$$ which are congruent as sets and, indeed, have all members congruent.

It is interesting to note that, If you triangulate an $$m$$-gon $$P$$ into $$k \geq m-2$$ triangles and follow this procedure you get $$kn^2$$ triangles in $$k$$ congruence classes. These can be assembled into $$n^2$$ congruent $$m$$-gons similar to $$P$$ and triangulated in the same way.

Define $$k_n$$ to be the least $$k$$ such that every triangle can be further triangulated into $$nk_n$$ small triangles with $$k_n$$ congruence classes. Equivalently, into $$n$$ pairwise congruent sets (in the sense of the question) each of size $$k_n.$$ Then certainly any $$m$$-gon can be partitioned into $$(m-2)$$ triangles and then into $$n$$ pairwise congruent sets each of size $$(m-2)k_n.$$ It seems plausible that this is optimal, though justifying that with a proof might be a challenge.

• We know that $$k_n \le n.$$
• $$k_{t^2}=1$$
• If $$n=st^2$$ with $$s$$ square free, then $$k_n \le k_s$$

It seems plausible that $$k_{st^2}=k_s,$$ but, again, that is not a proof.

However it seems most fruitful to concentrate on $$k_s$$ For $$s$$ square free.

• $$k_2=2$$
• $$k_3=2$$ (split into kites then bisect each).
• $$k_{ab} \leq k_ak_b$$ since we can partition each of $$k_a$$ types into $$k_b$$ subtypes. In particular:
• $$k_{3s} \le 2k_s$$

I suspect that $$k_p=p$$ for prime $$p \neq 2.$$ If so, then the last result is the only interesting use of the previous result.

• Thanks very much. The idea of getting n^2 mutually congruent m-gons similar to P is a nice bonus! The only bit remaining would be to decide whether this also gives the least number of pieces in each congruent set - for ex, if one starts with an octagon that has to be cut into 5 congruent sets, the octagon goes into 6 triangles each of which goes into 25 self-similar triangles and the resulting 150 pieces get grouped into 5 sets of 30 pieces each. Commented Nov 7, 2021 at 9:36
• @NandakumarR Do you mean uniformly for all octagons? Certainly some octagons have solutions for $n=2$ or $4$ that only use $n$ pieces. Do you only want convex polygons? Use four small squares to make a larger one. Place a fifth small square centered on the top to get a (nonconvex) octagon from 5 squares Commented Nov 7, 2021 at 19:06
• Thank you Prof Meyerowitz. Let me restate the last question better: your algorithm yields (m-2)*n pieces in each congruent set when cutting an m-gon into n sets. Is that a tight lower bound on the number of pieces per set when partitioning any general m-gon into n sets? Basically, is the algorithm optimal in minimizing number of pieces per set? Commented Nov 8, 2021 at 2:16