3
$\begingroup$

Is the following claim valid?

Claim: Given any planar convex region C, the thinnest cover of the plane with copies of C cannot have any region where more than 2 copies overlap. In general, the thinnest n-fold cover of the plane with copies of C cannot have regions where more than n+1 copies overlap. Copies of C are allowed to be rotated.

Note: The question can be asked in higher dimensions and in non-Euclidean setting. If C is allowed to be non-convex, the thinnest cover of the plane with C units might have regions where arbitrarily large number of units overlap.

A related issue was raised in On Covering a Planar Region with Copies of a Tile of Different Shape

A very elegant 2-fold covering of the plane is shown at: Thinnest 2-fold coverings of the plane by congruent convex shapes

$\endgroup$
5
  • $\begingroup$ What does "thinnest" mean in this context? $\endgroup$ Apr 30, 2022 at 4:42
  • 1
    $\begingroup$ If C does not tile the plane, if we cover the plane with copies of C, there have to be regions where more than one copy of C overlap. By thinnest cover, we mean that covering layout of the plane such average over points on the plane of the number of copies of C that overlap at that point is to be minimized. $\endgroup$ Apr 30, 2022 at 18:51
  • 1
    $\begingroup$ The Claim is stated ambiguously, since "the" coverings of minimum density is never unique. For instance, any given thinnest covering of the plane with congruent copies of a convex region C can be enlarged by an ARBITRARILY PLACED additional FINITELY MANY copies of C, which never affects the covering's density, while certainly can increase the maximum number of overlapping copies of C. $\endgroup$ Apr 30, 2022 at 20:19
  • $\begingroup$ Thanks for the correction. Your paper referenced below says thinnest means "most economical". So, is it that to achieve what is intuitively a thinnest cover, one ought to minimize BOTH the average over points on the plane of the number of copies of C that overlap at that point AND the maximum number of copies that overlap at any given point? $\endgroup$ May 1, 2022 at 11:47
  • $\begingroup$ @NandakumarR Intuition can deceive. Most of the time it happens so that when one quantity decreases, another one increases, and vice-versa. Density of an infinite arrangement (packing or covering) of convex bodies is defined analytically, usually involving computations. Formal, rigorous definitions can be found in the mathematical literature on packing and covering. $\endgroup$ May 1, 2022 at 21:35

1 Answer 1

1
$\begingroup$

See the example, a certain convex pentagon, presented in the joint paper by A. Bezdek and me:

Unavoidable Crossings in a Thinnest Plane Covering with Congruent Convex Disks, Discrete Comput. Geom. 43 (2010), no. 2, 187–208, MR2579691.

enter image description here

Besides its main purpose (unavoidable crossings), the very same example shows that your claim does not hold.

$\endgroup$
4
  • $\begingroup$ hanks! I understand that with copies of pentagon P_eps given above, for the thinnest cover of the plane : (1) first form a regular hexagonal tiling of the plane and then (2) cover each regular hexagon with 3 P_eps units - and this gives regions where 4 pentagon units overlap. Thus we seem to have that for the thinnest 1-cover of the plane with P_eps units, there already are regions with 4 (>2) units of P_eps overlapping. So, a natural question would be if there is an upper bound for number of units overlapping in the thinnest covering of the plane with copies of any given convex unit. $\endgroup$ Apr 30, 2022 at 19:01
  • 1
    $\begingroup$ @NandakumarR: Actually, there is another thinnest covering with copies of P_ε in which only triples of "units" overlap. After the first hexagon is covered with three "units", to cover each of the remaining hexagons use parallel translations (no rotation) from the first one. This way no quadruples will overlap, only triples. $\endgroup$ May 1, 2022 at 19:45
  • $\begingroup$ @MattF Thanks a lot for your kind help with composing my answer. $\endgroup$ May 1, 2022 at 19:49
  • $\begingroup$ Thanks for that nice argument, Prof Kuperberg. But 3 units overlapping is enough to exceed the initially guessed bound. Maybe 3 is a bound that cannot be exceeded for that thinnest covering of the plane with any convex unit which also minimizes the number of units overlapping at any given point. Of course, I can only wonder what can be said in 3D etc! $\endgroup$ May 2, 2022 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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