27
$\begingroup$

Let $C$ be a convex shape in the plane. Your task is to cover the plane with copies of $C$, each under any rigid motion. My question is essentially: What is the worst $C$, the shape that forces the most wasteful overlap?

To be more precise, assume $C$ has unit area. Let $n_C(A)$ be the fewest copies of $C$ (under any rigid motions) that suffice to cover a disk of area $A$. I seek the $C$ that maximizes the "waste": $$ w(C) = \lim_{A \to \infty} n_C(A) / A \;.$$ So if $C$ is a perfect tiler of the plane, then $\lim_{A \to \infty} n_C(A) = A$ (because $C$ has area $1$) and $w(C)=1$, i.e., no waste.

Consider a regular pentagon $P$, which cannot tile the plane. Here is one way to cover the plane with regular pentagons:

          TilerPentagon
If I've calculated correctly, this arrangement shows that $w(P) \le 1.510$. So one could cover an area $A=100$ with about $151$ unit-area regular pentagons, a $51$% waste. I doubt this is the best way to cover the plane with copies of $P$ (Q3 below), but it is one way.

Three questions.

Q1. Is it known that the disk is the worst shape $C$ to cover the plane? My understanding is that L.F.Tóth's paper[1], which I have not accessed, establishes this for lattice tilings/coverings. Is it known for arbitrary coverings?

Q1 Answered. Thanks to several, and especially Yoav Kallus, for pointing me in the right direction. Q1 remains an open problem. In [2,p.15], what I call the waste of a convex body $C$ is called $\theta(C)$. It is about $1.209$ for a disk. The best upperbound is $\theta(C) \le 1.228$ due to Dan Ismailescu, based on finding special tiling "p-hexagons" in $C$. A p-hexagon has two opposite, parallel edges of the same length.

Q2. Since every triangle, and every quadrilateral, tiles the plane, the first interesting polygonal shape is pentagons. What is the most wasteful pentagon?

Q3. More specifically, what is the waste $w(P)$ for the regular pentagon?

[1] L. Fejes Tóth, "Lagerungen in der Ebene auf der Kugel und im Raum." Die Grundlehren der mathematischen Wissenschaften Vol. 65. Springer-Verlag, 1972. doi:10.1007/978-3-642-65234-9

[2] Brass, Peter, William OJ Moser, and János Pach. Research Problems in Discrete Geometry. Springer Science & Business Media, 2006.

Improve this question
$\endgroup$
28
  • 3
    $\begingroup$ How about a house? (Square plus triangle) Gerhard "Welcome To The Suburban Future" Paseman, 2016.12.03. $\endgroup$
    – Gerhard Paseman
    Commented Dec 4, 2016 at 2:30
  • 8
    $\begingroup$ Any pentagon with two parallel sides tiles the plane. (See for instance the first picture in 3.bp.blogspot.com/-2YKhXVT62rc/Vd2KGHpYwnI/AAAAAAAAGWU/…) $\endgroup$
    – Noam D. Elkies
    Commented Dec 4, 2016 at 2:36
  • 4
    $\begingroup$ However, you can use these good tilers to estimate the ratio. Pick a good tiler nearest the shape of the bad tiler and embed a scaled down copy into the bad tiler. The best scale factor among many choices should allow a good estimate of the waste factor. Gerhard "It Is Like Urban Renewal" Paseman, 2016.12.03. $\endgroup$
    – Gerhard Paseman
    Commented Dec 4, 2016 at 2:52
  • 7
    $\begingroup$ As an example of Gerhard Paseman's recent comments, we get a waste ratio of only $w = (5+\sqrt{80})/11 < 1.2676611$ (if I computed right) for regular pentagons $P$ by finding a pentagon $P' \subset P$ of area $|P|/w$ that has two parallel sides and thus tiles the plane: fix a side $s$ of $P$, and let $P'$ consist of all points of $P$ that project to a point of $s$. $\endgroup$
    – Noam D. Elkies
    Commented Dec 4, 2016 at 3:03
  • 4
    $\begingroup$ re:Q1, Brass, Moser, and Pach have a good summary of results in their book books.google.com/… $\endgroup$
    – Yoav Kallus
    Commented Dec 4, 2016 at 18:17

1 Answer 1

Reset to default
16
$\begingroup$

Here is a better (possibly best) way of covering the plane with congruent regular pentagons:

  PentCover
The density of this covering is ${\sqrt5}/2 = 1.1180...$. This covering is generated by the maximum-area $p$-hexagon contained in $P$, and is the thinnest among all coverings with $P$ that are of the double-lattice type. I conjecture that this density is minimum among all coverings with $P$, not just double-lattice ones.

For the notion of double-lattice see: Kuperberg, G.; Kuperberg, W. (1990), Double-lattice packings of convex bodies in the plane, Discrete and Computational Geometry, 5 (4): 389–397, MR 1043721

This covering is obtained by a continuous transition starting with the best packing with regular pentagons, see http://www.auburn.edu/~kuperwl/pent_movie.mp4

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ Joe: As far as I know - no, but yes, I do think that the regular pentagon is the worst pentagon for covering. Some of its affine images may be equally bad, though. $\endgroup$
    – Wlodek Kuperberg
    Commented Dec 6, 2016 at 4:17
  • 3
    $\begingroup$ No. "Raising the roof" does not make the pentagon worse; it makes it better. Namely, in the modified pentagon one can use a different corner for the overlap; most efficiently the one at which the angle is greatest. $\endgroup$
    – Wlodek Kuperberg
    Commented Dec 6, 2016 at 4:28
  • 2
    $\begingroup$ For some people orange and green colors, of similar darkness, flash and get confused with each other... Otherwise great answer! $\endgroup$
    – Yaakov Baruch
    Commented Dec 6, 2016 at 7:16
  • 3
    $\begingroup$ @YaakovBaruch: colors changed in the picture; working on the animation. $\endgroup$
    – Wlodek Kuperberg
    Commented Dec 18, 2016 at 3:17
  • 1
    $\begingroup$ Actually this is precisely the covering I suggested in my last comment to the question; my computation was $w(P )\le5/4$ $\endgroup$
    – Pietro Majer
    Commented Dec 18, 2016 at 17:38

You must log in to answer this question.

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