10
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – The Masked Avenger
    Commented Aug 24, 2013 at 5:12
  • $\begingroup$ 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? $\endgroup$
    – The Masked Avenger
    Commented Aug 24, 2013 at 5:14
  • $\begingroup$ An attractive viewpoint, TMA! It reconnects it to the literature on tiling. $\endgroup$
    – Joseph O'Rourke
    Commented Aug 24, 2013 at 12:19

1 Answer 1

Reset to default
11
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Very nice, Yoav! Better and simpler. $\endgroup$
    – Joseph O'Rourke
    Commented Aug 23, 2013 at 16:47
  • 1
    $\begingroup$ 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). $\endgroup$
    – Yoav Kallus
    Commented Aug 23, 2013 at 18:41
  • $\begingroup$ Impressive! I checked your calculations because at first I didn't believe them :-). $\frac{1}{8}$ is surely the minimum. $\endgroup$
    – Joseph O'Rourke
    Commented Aug 24, 2013 at 16:58
  • $\begingroup$ 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. $\endgroup$
    – Manfred Weis
    Commented Aug 25, 2013 at 9:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .