Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I've encountered a tiling problem with a physical constraint that might place it outside the literature on tiling. "Tiling" is a bit of a misnomer; it is a special type of cover.

All the tiles are identical (congruent), convex shapes $S$. Layer 1, $L_1$, is some infinite pattern of copies of $S$ arranged on the plane with pairwise disjoint interiors. Layer 2, $L_2$, is the exact same pattern as $L_1$, but after some rigid motion of the whole arrangement (translation, rotation, perhaps reflection). Together $L_1$ and $L_2$ cover the plane: $L_1 \cup L_2 = \mathbb{R}^2$. But I want the center of gravity (c.g.) of each tile of $L_2$ to be on top of a point of some tile in $L_1$. Consider this last requirement an abstraction of a balance or support constraint. Finally, I would like to minimize double coverage, i.e., $L_1 \cap L_2$.

Below are some examples. Two penny packings of the plane (a), with $L_2$ shifted by the radius of the disk, satisfy the constraints. But if I've calculated correctly, 81% of the plane is doubly covered—not very good. The staggered squares in (b) improve the double coverage to $\frac{1}{3} =$ 33%. Here the c.g. of each $L_2$ square sits on the meeting of two corners of squares from $L_1$. One can improve this tiling by clipping off a corner (1/8-th) of each square, as in (c). Now the c.g. of each $L_2$ tile sits over an interior point of an $L_1$ tile. I calculate this reduces double coverage to $\frac{2}{9} =$ 22%.
         Tiling2abc
Because the c.g. in (c) sits over an interior point, there is room for improvement. Below in (d) I clip off a tiny portion of the opposite corner (shown in green) to move the c.g. to the boundary, resulting in a tiny improvement to 21.8%.
     Tiling2d

I have no reason to believe this is an optimal, or even a good tiling under these constraints. It seems there should be some fundamental positive lower bound to the double coverage, but I am not seeing an argument to establish such a bound.


Update1. Improved by Yoav Kallus to 19.8% double-coverage with a simpler construction! So the outstanding issue is: Lower bound?? Update2. Surely Yoav's new 12.5% tiling made of overlapping equilateral triangles is the optimal.

share|improve this question
1  
An alternate (perhaps equivalent) perspective is to look at polygons P that tile the plane and admit a presentation as the union of two minimally overlapping convex polygons satisfying the constraint. You might quickly show/refute Kallus's bound for the rectangle tile. –  The Masked Avenger Aug 24 '13 at 5:12
    
Further, pick two copies of your favorite narrow rhombus so that they satisfy the constraint with minimal overlap. Can this diamondized T shape be used to tile the plane effectively? –  The Masked Avenger Aug 24 '13 at 5:14
    
An attractive viewpoint, TMA! It reconnects it to the literature on tiling. –  Joseph O'Rourke Aug 24 '13 at 12:19
add comment

1 Answer

up vote 6 down vote accepted

The pentagon $(0,0)(0,1)(1/2,1+x)(1,1),(1,0)$ with $x=(\sqrt{21}-3)/4$ gives a double coverage fraction of $x/2=0.1978\ldots$.

enter image description here

UPDATE: The triangle can get you $1/8=0.125$

enter image description here

share|improve this answer
    
Very nice, Yoav! Better and simpler. –  Joseph O'Rourke Aug 23 '13 at 16:47
1  
If there is a lower bound on the distance from the center of mass to the boundary in some "isotropic" position (seems like there should be), that would give you a lower bound on the double coverage under the assumption that each layer is a lattice and one layer is a 180-degree rotation of the other (like all the coverings in this question so far). –  Yoav Kallus Aug 23 '13 at 18:41
    
Impressive! I checked your calculations because at first I didn't believe them :-). $\frac{1}{8}$ is surely the minimum. –  Joseph O'Rourke Aug 24 '13 at 16:58
    
A "soft-comment" on the statement and the solution of the problem: both are very nice examples that illustrate what qualifies one as a mathematician: an open eye for interesting questions and power of imagination for their solution; could be a good answer to the question why people become mathematicians. –  Manfred Weis Aug 25 '13 at 9:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.