Packing Rectangles

Here is a puzzle to which I dunno the answer yet.

Claim: Given N (N>1) rectangles all of the same area but all with different perimeters.
We cannot pack them without gaps to form a large rectangle.

IOW, if a rectangle is broken into N smaller rectangles all of same area, at least two of the pieces are identical.

Remark: it is not too hard to show rectangles which can be divided into N equal area rectangles with just 2 pieces identical, and all others having different perimeter.

Perhaps the claim may be easier to prove under the constraint: the sides of the rectangle and the pieces ought to be integers/rationals.

The following pages may be of interest.
http://mathdl.maa.org/images/upload_library/22/Ford/Wagon601-617.pdf
http://www.math.uwaterloo.ca/navigation/ideas/articles/honsberger2/index.shtml

Congruent Partitions - A Special Case

Question: Let us say, we cut from a convex polygon P 2 mutually congruent pieces such that the pieces have as great an area as possible. Find that polygon P which causes the maximum wastage - the fraction of the area wasted to the total area of P.

P is constrained to be convex with the pieces allowed to be non-convex. Which shape of P gives highest 'wastage fraction'? Basically, we need to upper-bound the wastage fraction when a convex P is 'maximally congruent bisected'.

A simple fact: The two maximum area pieces have to touch each other; indeed, otherwise both pieces could be moved in the interior of P (which is convex) to a config where neither piece touches the walls of P or each other - and from that stage, both pieces can be expanded identically => the area of the pieces were not max to begin with.

Another Congruent Partition Problem

A bit of news: The basic Congruent partition problem has been listed at:
http://maven.smith.edu/~orourke/TOPP/P73.html

Question: Given a convex polygon P and a number N so that P can somehow be cut into N mutually congruent *non-convex* pieces with no wastage - ie. a 'perfect congruent partition' exists for P for that N. Then is it true that P necessarily also allows a partition into N mutually congruent convex pieces?

In other words, can we say: "there is no P and N such that P can be perfectly congruent-partitioned into N pieces only when the pieces are necessarily non-convex"?

For N = 2, the above question seems to have an affirmative answer - no convex polygon appears to have only a congruent 2-partition such that pieces are non-convex. Beyond N=2, nothing much seems to be known.

'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).

A Doubt On Circle Packing

We understand that for packing identical circles (indeed packing copies of any centrally symmetric convex shape) in an infinite plane, the best arrangment is a always a lattice arrangement (hexagonal lattice for packing circles).

Does the above lead naturally to the following?

Consider any specified 2d shape as a container for identical circles.

Claim: Some finite critical magnification(scaling) of this shape exists such that
1.the best packing in it of circles is a hexagonal lattice of circles arranged inside and
2.for any further scaling up of this shape the best pack is the hexagonal pack.

This implies: If the container is a square, there is some critical size of the square beyond which the best circle packing of unit circles is ALWAYS the hexagonal lattice.

Some more thoughts on 'automatable' arrangments to follow...

Update (3rd May 2009): The main guess above is invalid. For the square the hex lattice is tbe best packing only in the asymptotic limit, as the square goes to infinity and is the same as the plane itself. No finite threshold and stuff. This is a bit surprising to me but that is how things probably are!

Fair Partitions - Article

After all those 'work in progress' posts on the polygon partitionig problem we posed (a series which went on for well over a year), we collected whatever we thought up into a proper article. It can be read at:

http://arxiv.org/abs/0812.2241

Note: The article is on the longer side since we try to develop the themes at a leisurely pace and try to give several illustrative examples. Hope it reads well, and even more importantly, that our arguments are logically tight. Right now, the jury is out...

Fair Partitions - 2^N?

We (Ramana Rao and self) consider here a recursive scheme for extending our polygon partitioning conjecture to 2^N. This approach is a variant of a naive recursion on N=2, which does not work - as argued in the post 'Fair Partitions -V':

------------
The conjecture: Given any positive integer N, any convex polygonal region allows partitioning into N convex pieces such that every piece has the same area and perimeter.
------------

Definitions:
-----------
We define a 'diagonal', as a line that divides a convex polygon into two pieces of equal area; their perimeters could be different (the diagonal could be between any two points on the boundary, not necessarily vertices).

Let us further call a line which divides a convex polygon into 2 pieces of equal area and equal perimeter a 'fair bisector'. Of course, a polygon can have just one fair bisector ( eg: for an isosceles triangle with very narrow base), a few or even infinitely many (a square for example) depending on its symmetry.

The Scheme:
----------
Divide input polygon into two equal area pieces by a diagonal; call these pieces A and B. Consider a *fair bisector* of piece A, dividing A into {A1, A2} - where A1 and A2 have equal area and equal perimeter. Likewise consider a fair bisector of B which gives pieces {B1,B2}. Initially, let us say the pair of pieces A1-A2 have higher perimeter than the pair B1-B2.

Rotate the *diagonal* continously; then, the pieces A and B change continuously maintaining equal areas; the two fair bisector lines also keep changing. Finally the diagonal reaches a position that is perfectly reverse of its initial position. Now, pieces A1-A2 have less perimeter than pair B1-B2 - they have merely exchanged their initial positions. By a continuity argument, we have somewhere along the rotation of the diagonal, a state where the two pairs had the same perimeter.

This could settle the conjecture for N= 4. Repeating the recursion, we could even prove the claim for N= 2^n. And if the conjecture could be proved for any number m, this could give a ready extension to N= m * 2^n

Possible Catch:
--------------
It needs to be shown that if a polygon is *continuously changed*, its fair bisector(s) change continuously - by a line segment moving continuously, we mean both its end points move continuously (of course, the length, orientation,etc of the segment as a whole could change).

Take a square and slightly and continously make it asymmetric, keeping its area constant; the new polygon might have only a few or just one fair bisector. this means most fair bisectors have simply *disappeared* by a continous transformation.

A more general case:

Consider a case where the fair bisector of piece A is such that sub-piece A2 covers the bisector entirely, ie. the fair bisector of A connects two edges of the input polygon and does not touch the diagonal which demarkates A and B.

Now let diagonal rotate a little, continuously, keeping the areas of pieces A and B same.Then, perimeter of piece A2 changes while A1 is *unaffected*. Of course, the areas of A1 and A2 remain equal. The net result: a difference just begins to develop between perimeters of A1 and A2.

Now, we need to change the fair bisector between A1 and A2 continuously to cancel out the perimeter difference that has emerged (due to the rotation of the diagonal) between A1 and A2. And we need a guarantee that such a continous change is possible for the entire rotation of the diagonal. What we need to prove is: at least one fair bisector of piece A - call this b(A) - and a fair bisector of piece B - call this b(B) - are such that as diagonal moves by a total of 180 degrees, b(A) continuously moves to b(B); a further movement of 180 of diagonal will cause b(B) to return to b(A).

Note : The new recursive scheme puts a constraint on the fair partitioning, a constraint we were not keen to put:

A general convex partitioning need not have two pieces meet in the interior of the polygon at 180 degrees - they only need to be convex.

In the recursive scheme A1 and A2, if they meet in the interior of polygon, are forced to together form an angle of 180 degrees. In the final partitioning, two pieces A1 and A2 together are forced meet the other two pieces along a straight line.

Update (12-9-08):
----------------
Let us call fair bisectors which are the result of symmetry and which cannot change continuously (and which merely vanish) when a polygon is slightly changed, 'bad bisectors'; those fair bisectors which do change continuously are good ones.

Our scheme seems to need the following to hold: Given two equal area convex polygons which share an edge (and together form a convex polygon). The number of 'good fair bisectors' of both these polygons are necessarily equal.

Indeed, if at a given position of a *diagonal*, the two equal area pieces A and B have different numbers of good fair bisectors, we would begin to doubt if one of A can actually continuously change all the way to one of B (as the diagonal does a 180 degree sweep) and vice versa.

Example:
We could check that the pentagon formed by points:
{(0,0),(6,20),(12,0),(12,-7.947),(12-.92, -19.39075)} has 3 good fair bisectors.
Consider the triangle:
{(0,0),(12-.92, -19.39075),(7,-55.53)}.
This triangle shares an edge with the pentagon, has the same area and together with the pentagon forms a convex polygon.
=> the common edge is a 'diagonal' of the big polygon formed by the pentagon and triangle.

Now, the triangle has only one fair bisector =>
some evidence that when the diagonal moves thru 180 degrees, the fair bisectors *need not* evolve continuously throughout the evolution of the diagonal.

Update (October 22, 2008):
-------------------------
Further experiments have confirmed that the fair bisector(s) of a polygon *may not* evolve continuously as the polygon is continuously deformed (keeping its area constant). But, (crucially!) for this new recursive scheme to work, we do not really need the fair bisectors to keep changing continuously - only the *perimeters of the pieces resulting from the fair bisectors need to change continuously*. In all examples tested so far, the perimeters do change continuously.

No logical proof yet either that the perimeters of pieces resulting from fair bisection of a polygon necessarily change continuously when the polygon itself is changed continuously. Work in progress...