TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Thursday, December 26, 2013

On Congruent Partitions of Polygons

A claim that looks plausible to me:

--------------

If any given convex 2D region C *does not* allow any of the following 3 types of parttitions:

a. division into any finite number of congruent triangles

b. division into any number of congruent convex quadrilaterals

c. division into any number of congruent convex regions such that no one piece is bounded by other pieces on more than two sides - ie, the pieces are arranged with all sharing a common vertex or with a chain-like topology (in the chain case, the orientation of the pieces need not all be alike).

then, for any finite n>1, C does not allow any partition into n mutually congruent regions, convex or otherwise.

Note: An obvious implication of this claim is allowing non-convex pieces will not enable a 'congruent partition' of any convex region that does not allow partition into convex congurent pieces.

--------------

Now, let me point to this page .

On the solutions page , the following statement is proved:

--------------

Let P be a convex quadrilateral whose angles are linearly independent over the rationals; that is, no nontrivial integer linear combination of the four angles gives 0. For example, consider: α1=180/√(5), α-2=180/√(7), α3=180/√(11), α4=360-α1-α2-α3. For any positive integer n >1, such a P does not allow any partition into n congruent pieces.

--------------

We note that if the claim at the top is valid, Ponder's proof shortens a great deal. Indeed, assuming the claim, it is easy to see that for such an 'irrational quadrilateral' one only needs to rule out partitions into congruent triangles or convex quadrilaterals (no need to consider pentagons as likely pieces as Ponder does) and both are easily done.

Note added on January 5th 2014: The claim *might* allow some further tightening. Case b above may not even be needed. There may be no convex shape that (1) cannot be cut into congruent triangles but (2) can be cut into congruent convex quadrilaterals such that the pieces *need* to have an arrangement more complex than an unbranching chain. So, to rule out congruent partitions of a convex shape, one might need to only rule out partition into congruent triangles and partition into *chains* of convex congruent polygons.