Covering With Rectangles

Note: The question statements have been upgraded following a comment from Prof. Joseph O'Rourke

Given a convex 2D region C and a positive integer N. We need to cover C with N rectangles so that the sum of the areas of the N rectangles is the least – no further constraints on the dimensions of the rectangles. Then,

1. Are we guaranteed to get 'an optimal N-rectangle cover' of C if we insist that the orientations (direction of the length) of all N rectangles ought to be the same? (Note: If the answer is "yes", finding algorithms for 'optimal N-rectangle cover of C' would become easier)

2. If answer to (1) is "yes", one can ask: for the same C, if N is varied, can the orientations of the 'optimal rectangle covers of C' always be chosen for every N from a very small set? One guesses for any given C, one can choose from only 2 possible orientations and get an optimal rectangle cover of C for any N.

3. If both above questions have a "yes" answer, do the above properties hold even if we replace 'rectangles' with 'ellipses' or with any other convex shape with a center of symmetry? And yes, are there higher dimensional analogs?
------------------
Note: Similar questions can also be asked about N rectangles put inside C such that they together cover the maximum portion of C. Is the best such configuration of N rectangles inside C always one where the rectangles do not overlap?
The answer for this question appears to be that insisting the rectangles to be of same orientation could lead to a suboptimal solution. See this picture:

For the given right triangle, with N=2, if the inner rectangles have to be of same orientation, at most only 2/3 of the right triangle appears coverable. However, as in the second configuration with 2 red rectangles which overlap and are oriented differently, we have a coverage of 3/4 which can even be further improved.
------------------
Update (August 3rd 2019)
On question 3 above: Extending of the claim on rectangles to regions with central symmetry has problems. Indeed, it is easily shown to be so for rhombuses. See picture below. A pentagon shown covered by 2 rhombuses (black and blue) which are not aligned in the same direction. No other pair of rhombuses appears to give a better coverage.

However, the pentagon can be covered with 2 non-overlapping parallelograms parallelly aligned to each other and with the same combined areas as the blue and black rhombuses shown above.

'Mixed' Packing of the Plane

The basic question: to pack the plane efficiently - without overlaps - using more than one type of unit. In particular let us consider packings with 2 types of units.

Packing the plane with two types of units - call them C1 and C2 - seem to belong to two categories - where the relative numbers of the 2 types of shapes are equal and where they are not. 'equal number' is used here in the sense that the plane ought to be filled with an 'alloy' which consists of C1 and C2 units in equal proportion. One feels that the equal numbers case is more interesting.

Example: We need to pack the plane with maximum coverage using unit disks and unit squares both in equal number.

A simple approach which might be optimal: pack a half plane optimally with unit circles alone (Note: the hexagonal lattice is known to be the best layout with unit circles if the entire plane is to be packed. It is very likely the best way for a half plane as well) and the other half plane can be tiled with unit squares. One needs to be careful as to how the two half-plane lattices meet at their interface.

--------
We could also think of homogeneous layouts using both disks and squares. By homogeneous, one could mean: for any sufficiently large real number r1 and any point on the plane P, if a circle with radius r1 centered at P contains or intersects more disks than squares then, there is some other real number r2 >r1 such that a circle with radius r2 centered at P intersects more squares than disks. And if the same condition holds for any center P and also with 'disk' and 'square' interchanged, then the layout is homogeneous. Homogeneity of a 2-unit layout formed by C1 and C2 can also be viewed as the property that every C1 unit has among its neighbors at least as many C2 units as C1 units and vice versa.

Questions: Which homogeneous layout of unit disks and squares gives maximum coverage of the plane? (On the other hand, which homogeneous layout of disks and squares gives the thinnest rigid pack of the plane?)
-----------
On a more general note: Consider any two convex regions C1 and C2 satisfying some additional properties such as say, equal area or equal area and perimeter (unit disk and unit square are not of equal area). Can one have some 'sweeping' results such as (say): "the max coverage pack of the plane using C1 and C2 in equal numbers is necessarily formed of two half planes one packed with C1 and the other with C2. IOW, any kind of mixing of the units leads to reduced coverage"? Oppositely, are there pairs of convex equal area shapes for which the best plane packing is a homogeneous one? What could one say about periodicity / aperiodicity of such optimal mixed packings?

Obviously, similar questions can be asked for covering the plane and for packing in higher dimensions.
----------

Further Question 1: Are there pairs of convex shapes of equal area such that the layout of maximum packing coverage using both (with no homogeneity requirement) necessarily has them in a ratio other than 1:1?
Here is an example

That is a perfect pack of the plane with 'chopped hexagons' (all these heptagons are identical although shown in 3 different colors) and equilateral triangles (all in yellow) with their relative populations in the ratio 3:1. No other layout - including the ones where the two shapes don't mix - appears to yield a perfect pack.

One can ask for pair of convex shapes with both shapes being of equal area and/or that pack the plane optimally when they are in other population ratios, say, 7:3.
-----------------
2. This is a variant of the Heesch problem (https://en.wikipedia.org/wiki/Heesch%27s_problem) - Given two convex regions C1 and C2 that together do not tile the plane. Starting with a single C1 unit, how many gap-free layers of tiles can be built around it using both C1 and C2 units, at least using one C2 unit in every layer - and without further constraints on their relative numbers? The question can just as well begin with a central C2 unit.

Obviously, with C1 and C2 being a square and a disk, we wont progress at all from the central unit. There must be {C1, C2} pairs such that the number of layers possible around a central C1 and the number layers around a central C2 are different. And then there is the 'wall' variant of the Heesch problem - https://arxiv.org/abs/1605.09203!

On Convex Layouts from Non-Convex Polygons

It is well known (for example Michael Reid's page ) that among non-convex polyominoes are several whose copies can team up to form a neat rectangle. And for several such rectifiable polyominoes (esp those with high order), the smallest rectangle that its copies form has a very non-trivial layout.

Polyominoes obviously are rectilinear polygons - all angles are 90 or 270 degrees). Consider non-convex polygons none of whose angles are 90 or 270. Is there any such totally non-rectilinear polygon P for which the convex polygon formed with least number of copies of P has a non-trivial layout?

Note: Obviously, there are non-convex polygons (equally, polyominoes) such that any number of copies cannot form a convex polygon (rectangle) together.

An example of a trivial layout: Consider a regular n-gon partitioned into n identical isosceles triangles radiating from its center. Replace all arms of the triangles with identical zig-zags. The regular polygon is now a layout of complex non-convex polygons but its topology is of a simple ring. Note that in many of the polyominos with high order, the topology of rectangular layouts with their copies is quite complex.

One can also ask for non-convex polygons with not all angles 90 or 270 for which the smallest convex region its copies form emerges from a non-trivial layout.

Tiling With Unique Neighborhoods - 2

Here, I try to gather what was written as an addition to this earlier post (https://nandacumar.blogspot.com/2019/03/more-on-2d-layouts-with-unique.html) into a proper self-contained post.

Given any region that can tile the plane (without gaps or overlaps) and a tiling layout with it: define the 'neighborhood' of any given unit tile T in the layout as the union of T and all other tiles in the layout that touch it.

Question: Does there exist a tile (not necessarily convex) that can form a tiling layout such that if we choose any two tiles in the layout, their neighborhoods are non-congruent?

Further, Is this question related to the 'Einstein problem', the question of finding aperiodic tilings with a single tile (An aperiodic tiling is a non-periodic tiling with the additional property that it does not contain arbitrarily large periodic patches)? Probably the two questions are different but I am not sure.... and yes, our question has obvious higher dimensional versions.

Some further thoughts:

It looks easy to a tile the plane with all neighborhoods non-congruent if we use two different species of tiles. Consider any rectangle A (A could be the unit square) and another rectangle B such that ratio between the dimensions of B to those of A are irrational. Form infinite strips of As and Bs and put them side to side thus: (1)keep one side of a unit in each of the strips - whether A-strip or B-strip - flush with the Y axis (all strips are now obviously parallel to X axis). (2) Now, keeping the A-strips fixed, slide each B-strip by a mutually independent small irrational distance in X direction. Such an arrangement looks enough to ensure that every unit rectangle - of type A or B - has a unique neighborhood.

We note here that there seem to be enough small irrationals (due to properties of the various 'alephs') to form an (countably) infinite number of different tilings for the plane - each with the unique neighborhood property - with the same A and B rectangles.
-------------------------------
Claim: With unit cubes, we can form a tiling (a tessellation, to be precise) of 3D space with every unit possessing a unique neighborhood.

Proof: Consider a corner to corner layout of identical squares that tile the plane. Assume the X and Y axes to be aligned along the edges of one of the squares. Call this tiling layout T1.

Now, consider another tiling layout T2 that is identical to T1 and lying directly on top of T1. Keeping T1 fixed, rotate T2 about Z axis by any angle α with its sine and cosine irrational and mutually linearly independent over rationals (there are infinitely many such values of α as per Niven's theorem, say). Now we can consider T2 to be formed by the basis vectors: (cos α, sin α) and (-sin α, cos α). Obviously, vertices on T2 are formed by linear combinations of these vectors with coefficients chosen from integers.
Let us call the fractional part of a number as its 'offset'. We observe that the offsets of the X coordinates (likewise, Y coordinates)of the vertices of T2 are all unique. Indeed, if two vertices on T2 have same X( or Y) coordinate, then, the X ( or Y) component of the vector joining these two vertices, which will be an integer, can be written as a linear combination - with integer coefficients - of sin α and cos α which is impossible due to irrationality. Now, every square in T1 is overlaid by a certain number of vertices and squares from T2. Since every 'T2 square' has unique offsets, we have: for every 'T1 square' S, the portion of T2 it sees has a unique position with respect to S (note that the T2 vertices that lie within S will have unique X and Y offsets).

Note: Observe that there is a 90 degree rotation symmetry to the above construction. This can be broken by translating T2 in a general 2D direction by some small irrational distance thus ensuring every S in T1 seeing a unique portion of T2.

Now, let all squares of layouts T1 and T2 be 'lofted' into unit cubes. It is easily seen for every cube from layer T1, the portion of T2 that is in contact with this cube is unique. And since there are infinitely many values of α by which we can go on rotating and stacking layers of cubes on top of each other, we can ensure every cube in the full 3D arrangement has a unique neighborhood.
-------------------------

Remark: Assuming the above argument to be sound, it appears that any shape such as the cube which allows 3-space to be tessellated layer by layer allows such layer-by-layer transformations that ensure every unit has a unique neighborhood. However, I don't know what to do for shapes that do tessellate 3D without allowing layer-by-layer buildup. And of course, in 2D, I have no idea yet as to tiling with a single shape and ensuring unique neighborhoods.

Note: None of the above arrangements - with 2 species of tiles in 2D or with 1 species in 3D - is aperiodic; indeed, they are built of infinite strips (or layers) that are periodic arrangements of identical rectangles (or boxes).