'Congruent' Partitions of Polygons

Here is another polygon partitioning problem, a work-in-progress thought:

Problem: Given a polygon P and an number N. We need to cut from
P, N mutually congruent (*) pieces (or 'tiles')of a suitable shape such that the area inside P is as fully covered by the pieces as possible.

(*) - two polygons are congruent if one can be made to
coincide totally with the other by translation, rotation or 'flipping
over'.

Note 1: It is known that a convex polygon *need not* admit a partitioning into N congruent pieces which together cover the whole of its interior. eg:
http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/December2003.html
(Part 2 of the 'challenge').

Guess: It seems this inevitability of there being a left-over (in some cases)is a 2D phenomenon. Any 3D input region appears cuttable into, say, 2 (or any N) identical and non-convex pieces which fill the whole of the input region in a very fractally way with dense and interpenetrating branches (somewhat like the two worms which eat up an anpple in Gamow's '1,2,3,infinity').

So, the problem requires us to choose the shape the identical pieces should have so
that as little area of the input polygon is left uncovered - or the
input sheet is as fully 'utilized' as possible.

-----------------
Further thoughts:
-----------------

1. Consider the following claim: for any N and for any input *convex* polygon, if we do the 'congruent partitioning' with the further condition that the identical pieces are also convex and find the best solution, it will also be the global optimum - ie. allowing the pieces to be concave leads to no better utilization of the input convex polygon.

This claim - that the best congruent partition of a convex polygon can be done with convex pieces - is *not true* it appears (thanks to Prof. Erich Friedman).

eg: Consider a 3X7 rectangle and remove a unit square from a corner; then form the *convex hull* of the resulting object, getting a pentagon or area 20.5. Out of this, an area of 20 can be filled by five L-tetrominoes - non convex objects. No convex congruent partition of this pentagon appears to leave such a small remainder.

Now, we float a new guess: the complexity of the piece (measured in the number of edges in it) in the best congruent partition is not more than linear in the complexity of the input polygon (here, Circular arcs are treated as no more complex than straight lines). There *probably* is no dependence of the complexity of the piece on N, the number of pieces. Basically, the guess is that if the input polygon has a 'simple' shape, the pieces in the best congruent partition cannot be highly branched and complex but comparable in complexity to the input polygon itself, for any N.

-----

2.If we relax the original requirement - to give N mutually congruent tiles - and seek N mutually identical *sets of tiles* (every tile of any set i is congruent to a tile in any other set j as i and j run from 1 to N), with each tile-set allowed to have finitely many pieces, we can do better in terms of reducing leftover:

Fact: Any triangle can be cut into 4 mutually congruent triangles; and any polygon can be divided into triangles. Any m-gon will give m-2 triangles.

So, If N is 4, we can triangulate the (m-vertex) input polygon and further divide each triangle into 4 so as to achieve a partition into 4 tile-sets each with m-2 triangles. This is easily generalizable to N = any power of 2. No bit of the input polygon is wasted.

Definition: A polygon is n-sectible if it can be cut into n mutually congruent pieces.

If N=3, we could try this: Somehow partition the input polygon into *some* number of pieces (each of which may be quite different from each other) such that each of them is 3-sectible; that will in turn enable a partition into 3 mutually identical sets of pieces with no leftover.

Note 1: 3-sectibility is a very loose property and is shown by a wide range of shapes. And it is not clear if any given polygon *always* allows partitioning into 3-sectable pieces (or in general, partitioning into m-sectable pieces) with no leftover.

Note 2: Even the apparently simpler (to state) problem: "given a polygon, determine if it is 3-sectible" appears unexplored - although there is work on partitioning a polygon into 3 pieces all of same area and same perimeter (eg: in the 'fair partitioning' context).