Dividing a shape into congruent subregions

Question

Given an irregular many face polygon with equal sides. Is there any algorithm to divide it into six equal sized congruent regions ??

Answer 1

No. Such subdivision is not always possible:

Consider the polygon P obtained by joining two regular polygons P1 and P2 with a different and very large number of sides N1 and N2. This polygon approximates a pair of circular disks C1 and C2 to within an arbitrary precision.

Consider a subdivision thereof into six congruent regions.

Consider the set of vertices of P1. There must be a region that contains at least (N1)/6 vertices. Call the vertices V1 and the region R1. There must be a region that contains at least (N2)/6 vertices of P2. Call the vertices V2 the region R2.

If R1 != R2, then there must be a congruence mapping R2 to R1. If 2*N1 < N2, such mapping is impossible. Choose N2 to be much larger than N1.

Thus, R1 == R2. There is a region that contains both V1 and V2. The diameter of each region must be larger than the diameter of P2.

Use the two-circle approximation. Each region must contain an arc of at least 1/6 of the perimeter of C1 and an arc of at least 1/6 of the perimeter of C2. Also, there is at least one region that is inside both circles and no region is entirely inside the smaller circle.

Consider the possible congruences of R1. Any congruence either 1) is the reflection along the main axis or 2) maps either P1 or P2 outside P or 3) maps some part of the perimeter to the interior of P. The reflection is not sufficient, so any subdivision must contain a congruence that maps some part of P1 to the interior of P1.

Thus, each region boundary must contain a concave arc with the diameter of 12. Intuitively, this shows such subdivision cannot exist.

---

There are many classes of polygons that you could detect:

• Order-6 rotation symmetry C6. These can be subdivided in any way that respects the rotation symmetry.
• Order-3 dihedral symmetry D6 (order-3 rotation + mirrors). Cut along the mirrors.
• shapes that tile the plane with translation with four polygons meeting at a vertex. These are the shapes that have two pairs of matching opposite paths. Duplicate the cutting edge in one direction and triplicate in the other.
• some shapes have a reflection symmetry and each individual half has an order-3 rotation symmetry. These can be detected and cut as well.
• some shapes have an order-2 rotation symmetry and can be cut in two congruent regions that have an order-3 rotation symmetry. Look for a repeated pattern along the boundary.
• some shapes have an order-3 rotation symmetry and can be split in three regions with a symmetry. I'm not sure I could reliably detect such shapes (detecting C3 is easy, subsequent cutting isn't) and I'm a human.
• ...
• polyominoes are shapes made out of squares, polyhexes are shapes made out of hexagons and polyiamonds are shapes made out of triangles. They are easy to detect and some even have a subdivision. The subdivision, if exists, may be difficult to detect as well, but at least you can enumerate all subdivisions that respect an aligned grid at the correct size to see if they are congruent.
• ...

To demonstrate the complexity of the problem: There is a certain class of logical puzzles where the goal is to split a complex shape (60 squares) in two congruent regions. If it is not easy for a human to split a polyomino in two congruent regions, how do you expect a computer to split a general shape in six congruent regions?

If you do want to detect the most cases where the subdivision is possible, you have to trade off between programming time (to support more and more special cases) and test strength. For starters, stick with C6, D3 and checkerboard tiles => easy to subdivide; polyforms => maybe possible; the rest => probably no subdivision.