Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 35 (1994), No. 1, 101-108.

Covering the Plane with Congruent Copies of a Convex Disk

Edwin H. Smith^{∗}

Department of Mathematics, Auburn University 255 Conway Acres, Auburn, AL 36830, U.S.A.

Abstract. It is shown that there exists a number d_{0}< 8(2\sqrt{3}−3)/3 = 1.237604.., such that every compact convex set K with an interior point admits a covering of the plane with density smaller than or equal to d_{0}. This improves on the previous result [9], which showed that a density of 8(2\sqrt{3} − 3)/3 can always be obtained. Since the thinnest covering of the plane with congruent circles is of density 2π/\sqrt{27} = 1.20919 …, we strengthen the case for the conjecture that the smallest such number d_{0} is 2π/\sqrt{27}.

I. Introduction

A convex disk is a compact convex set in the plane having an interior point. We will denote by K an arbitrary convex disk in the plane.

A packing of the plane with copies of K is a family {K_{i}} of sets congruent to K whose interiors are mutually disjoint. A covering of the plane with copies of K is a family {K_{i}} of sets congruent to K whose union is the plane. A family {K_{i}} which is both a packing and a covering is called a tiling. Any convex disk which admits a tiling is called a (convex) tile.

Suppose T is a tile and T is contained in (respectively contains) K. If {T_{i}} is a tiling with copies of T, then each T_{i} is contained in (contains) a copy K_{i} of K. Then {K_{i}} is a covering (packing) of the plane associated with the tiling {T_{i}}.

Throughout this paper, the area of any set S in the plane will be denoted by |S|. Each covering (packing) is assigned a non-negative number, called the density of the covering (packing), which, intuitively, corresponds to the ratio of the sum of the areas of the disks in the covering (packing) to the area of the region which they cover (pack). A definition of density and the detailed investigation concerning its existence and uniqueness can be found in [3, Section III, Chapter 1]. In the case that the covering (packing) {K_{i}} is associated

∗ This paper is based upon the author’s doctoral dissertation, defended at Auburn University November 8, 1994.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}1994 Heldermann Verlag, Berlin

with the tiling {T_{i}}, the density of {K_{i}} can be computed as |K|/|T |. For example, the density of the familiar ‘honeycomb’ circle packing is π/\sqrt{12}, and the circle covering by the same honeycomb pattern is of density 2π/\sqrt{27}.

Early in this century, A. Thue (1910, [14]) showed that the density of a packing of congruent circles in the plane never exceeds π/\sqrt{12}. Later R. Kershner (1939, [4]) proved that the density of a covering of the plane with congruent circles is never less than 2π/\sqrt{27}. It is a conjecture that every convex disk K admits a covering with congruent copies having density less than or equal to 2π/\sqrt{27}.

In this paper we investigate the following problem: find the least number d_{0} such that every convex disk admits a covering of the plane with density smaller than or equal to d_{0}. W. Kuperberg [9] has shown that d_{0} ≤ 8(2\sqrt{3} − 3)/3. In this paper we show that d_{0} < 8(2\sqrt{3} − 3)/3.

In a classical theorem [12], E. Sas showed that every convex disk K of area 1 contains an n-sided polygon P_{n} (n ≥ 3) with the area of P_{n} being greater than or equal to that of a maximal area (regular inscribed) n-sided polygon contained in a circle of area 1. If K is centrally symmetric and n is even, then by a theorem of Dowker [1], a centrally symmetric P_{n} can be found which is also of maximum area among all n-sided polygons in K. Since every centrally symmetric hexagon tiles the plane, it follows immediately that every centrally symmetric convex disk admits a covering of the plane with density smaller than or equal to 2π/\sqrt{27}. In view of the result of Kershner [4] mentioned above, the number 2π/\sqrt{27} is the least upper bound of covering density for centrally symmetric convex disks.

The analogous problem for packings of convex disks is investigated in [5], where the authors show that every convex disk admits a packing with density greater than or equal to \sqrt{3}/2 = 0.866025 . . .. The packing problem for centrally symmetric convex disks has been given more attention due to its role in the Geometry of Numbers. Tammela [13] has shown that any centrally symmetric convex disk admits a packing of the plane with density greater than or equal to 0.89265 . . .. This bound was obtained through an elaboration of a method of Ennola [2] who suggested this improvement of his own result. However, it is conjectured that the ‘smoothed octagon’ of Reinhardt [11], for which the packing density equals 0.90241 …, provides the best bound in this context.

II. Coverings associated with p-hexagons

A p-hexagon is a convex hexagon with a pair of parallel opposite sides of equal length, where ‘opposite’ means separated by two sides in each, clockwise and counterclockwise direction [6]. Extreme cases are allowed under this definition, in which some sides, even the parallel ones, may be reduced to points. Thus each convex quadrilateral is a p-hexagon, as well as each triangle. It is easy to observe that each p-hexagon tiles the plane (see Figure 1). This property of p-hexagons makes them very useful in obtaining associated packings of high density (see [8] and [9]) and coverings of low density (see [6], [7] and [8]).

The following theorem will produce the main result of this paper as a corollary.

Theorem. Every convex disk K contains an inscribed p-hexagon H with |H|/|K| > (2\sqrt{3}+ 3)/8.

Figure 1

We begin with a lemma. Lemma (W. Kuperberg [9]). Suppose that A = (A_{x}, A_{y}) and B = (B_{x}, B_{y}) are points in the first quadrant of the xy-plane with A_{x} ≥ B_{x} and A_{y} ≤ B_{y} and let OXCY be a quadrilateral such that O is the origin, X lies on the positive half of the x-axis, Y lies on the positive half of the y-axis, A lies on CX, and B lies on CY, and so that the complement of the quadrilateral in the first quadrant is convex. Then the area of the quadrilateral is greater than or equal to 2A_{y}(A_{x} −B_{x})+2B_{x}(B_{y} −A_{y}) and this minimum only occurs when A is the midpoint of CX and B is the midpoint of CY.

Figure 2

Proof. With A and B fixed, the position of C determines the entire quadrilateral (see Figure 2). We consider C a variable and the area of the quadrilateral as its function. The minimum of the function is achieved only when C is placed so that A is the midpoint of CX and B is the midpoint of CY. In this position of C, the area of the quadrilateral equals 2A_{y}(A_{x} − B_{x}) + 2B_{x}(B_{y} − A_{y}), which completes the proof.

Proof of the Theorem. The proof which follows is an extension of the proof from [9] which preserves the notation and construction illustrated by Figure 3, the figure itself being redrawn from [9]. Let k_{1} and k_{2} be a pair of parallel lines of support of K, such that K lies between them. The direction of the lines can be chosen arbitrarily. Let V_{1} and V_{2} be points at which k_{1} and k_{2}, respectively, touch K. Let \overline{W_{1}W_{2}} be a longest chord of K in the direction of k_{1}, and denote by m_{1} and m_{2} the parallel lines of support of K touching K at W_{1} and W_{2}, respectively. The lines k_{1}, k_{2}, m_{1} and m_{2} define a parallelogram containing K. The affine-invariant nature of the Theorem’s statement allows us to assume that the parallelogram constructed above is a square of side 4. Denote the vertices of the square by P, Q, R and S as shown on Figure 3. This figure illustrates some additional constructions and notations described as follows. Let ABCD be a parallelogram inscribed in K with sides AB and CD each of length 2\sqrt{3} and parallel to k_{1}. The vertices of ABCD should be arranged cyclically, in the same orientation as those of the square P QRS, and so that the side AB lies between \overline{W_{1}W_{2}} and k_{1}, while CD lies between \overline{W_{1}W_{2}} and k_{2}. Let EF GH be a parallelogram inscribed in K with sides EF and GH parallel to k_{1} and such that the distance between the lines EF and GH equals 2\sqrt{3}. The existence of these parallelograms is guaranteed by a continuity argument. Specifically, assuming K is strictly convex, chords of K which are parallel to k_{1} change continuously from a length of 0 to a length of 4 and back to zero as they move from k_{1} to k_{2}. In the event that the boundary of K contains a segment which lies in k_{1} or k_{2}, a chord can be grown continuously within the boundary. Notice that the length of EH and F G may be greater than 2\sqrt{3}. The vertices of EF GH should be arranged cyclically in the same orientation as those of P QRS and so that the side EF lies between \overline{W_{1}W_{2}} and k_{1} while GH lies between \overline{W_{1}W_{2}} and k_{2}.

Figure 3

Let x denote the length of the sides EF and GH and let y denote the distance between the lines AB and CD. We shall concentrate on two hexagons inscribed in K: the p-hexagon h_{1} = W_{1}EF W_{2}GH and the p-hexagon h_{2} = V_{1}BCV_{2}DA, whose areas are |h_{1}| = \sqrt{3}(x+4) and |h_{2}| = \sqrt{3}(y + 4). Let t = max(x, y) and let h denote h_{1} or h_{2}, whichever of these two p-hexagons is of area \sqrt{3}(t + 4).

Case I. t > 2\sqrt{3}. Then |h| > 4\sqrt{3} + 6, while |K| ≤ 16. Thus, |h|/|K| > (2\sqrt{3} + 3)/8. Case II. t ≤ 2\sqrt{3}. In this case, x ≤ 2\sqrt{3} which means that the segments EF and GH

are not longer than the segments AB and CD. Therefore the aforementioned 12 points are ordered cyclically W_{1}AEV_{1}F BW_{2}CGV_{2}HD on the boundary of K.

Now we consider the convex dodecagon d defined by the lines of support k_{1}, k_{2}, m_{1} and m_{2} along with the eight lines of support whose points of contact with K are A, E, F, B, C, G, H and D. Since d contains K we have |K| ≤ |d|. Notice that the complement of d in the square P QRS is the union of four quadrilaterals which we denote q_{P}, q_{Q}, q_{R} and q_{S}, their subscripts corresponding to the corner in which they lie. For each quadrilateral, introduce a separate coordinate system so that the corresponding corner of the square is the origin, the lines containing their horizontal or vertical side is the x-axis or y-axis respectively, and the quadrilateral lies in the first quadrant. Note that, as in the lemma, the complement of each quadrilateral in its respective first quadrant is convex. In their corresponding coordinate systems the points A, E, F, B, C, G, H and D have their corresponding coordinates A = (A_{x}, A_{y}), B = (B_{x}, B_{y}), etc., giving us the following equalities:

(1)  A_{x} + B_{x} = 4 − 2\sqrt{3},
(2)  C_{x} + D_{x} = 4 − 2\sqrt{3},
(3)  E_{x} + H_{y} = 4 − 2\sqrt{3},
(4)  F_{y} + G_{y} = 4 − 2\sqrt{3},
(5)  E_{x} + F_{x} = 4 − x,
(6)  H_{x} + G_{x} = 4 − x,
(7)  A_{y} + D_{y} = 4 − y,
(8)  B_{y} + C_{y} = 4 − y.

Additionally, since the lines AB, CD, EF, and GH are parallel to k_{1} and k_{2}, we have the equalities:

(9)  A_{y} = B_{y}, C_{y} = D_{y}, E_{y} = F_{y}, G_{y} = H_{y}.

Through use of the lemma, we gain the following inequalities:

(10)  |q_{P} | ≥ 2E_{y}(E_{x} − A_{x}) + 2A_{x}(A_{y} − E_{y}),
(11)  |q_{Q}| ≥ 2F_{y}(F_{x} − B_{x}) + 2B_{x}(B_{y} − F_{y}),
(12)  |q_{R}| ≥ 2G_{y}(G_{x} − C_{x}) + 2C_{x}(C_{y} − G_{y}),
(13)  |q_{S}| ≥ 2H_{y}(H_{x} − D_{x}) + 2D_{x}(D_{y} − H_{y}).

Adding inequalities (10)-(13) and using the equalities (1)-(9), we conclude that the area of the union of the four corner quadrilaterals is greater than or equal to 2(4 − 2\sqrt{3})(4\sqrt{3} − (x + y)), which is in turn greater than or equal to 8(2 − \sqrt{3})(2\sqrt{3} − t). Therefore

|K| ≤ |d| ≤ 16 − 8(2 − \sqrt{3})(2\sqrt{3} − t) = 8(2 − \sqrt{3})(4 + t),

which implies that

|h|/|K| ≥ \sqrt{3}/8(2 − \sqrt{3}) = (2\sqrt{3} + 3)/8,

with the equality only occurring when both of the following are satisfied: K = d and each of the points A, E, F, B, C, G, H and D are the midpoints of the respective sides of d which contain them.

Figure 4

Assume now that we have equality above. Let us consider the quadrilaterals q_{P} and q_{Q}. A side of these quadrilaterals which is shared with the dodecagon d has A, E, F or B as its midpoint. We denote these segments s_{A}, s_{E}, s_{F} and s_{B} respectively and denote the sides of K which are contained in m_{1} or m_{2} as w_{1} and w_{2} respectively (see Figure 4). Note that w_{1} and w_{2} may be degenerated to points. Since the midpoints and lower endpoints of s_{E} and s_{F} have identical y coordinates, their upper endpoints must also have identical y coordinates. Similarly, the upper endpoints of s_{A} and s_{B} have y coordinates which are the same. Likewise, q_{S} and q_{R} have common horizontal lines of support. Thus w_{1} is the horizontal projection of w_{2}.

Now we choose parallel lines of support of K (= d) whose angle of inclination differs only slightly from that of k_{1} and k_{2}. We denote these as k_{1}^{∗} and k_{2}^{∗} as illustrated in figure 5. In the case in which w_{1} and w_{2} are segments not degenerated to points, denote by p the line which is parallel to k_{1}^{∗} and passes through the lower endpoint of w_{1}. Through an affine transformation f from the plane onto the plane, we take the parallelogram defined by the lines m_{1}, m_{2}, k_{1}^{∗} and k_{2}^{∗} onto a square of side 4 (Figure 6) and repeat the above construction of an inscribed p-hexagon and a dodecagon containing f(K) which we denote as h^{∗} and d^{∗} respectively. We now observe (Figure 6) that f(w_{1}) is not the horizontal projection of f(w_{2}) and we therefore will not satisfy both of the conditions for the above extreme case in which |h^{∗}|/|f(K)| = (2\sqrt{3}+3)/8. In the event that w_{1} and w_{2} are reduced to points, a longest chord in the direction of k_{1}^{∗} can be arranged to have either w_{1} or w_{2} as one of its endpoints and the other endpoint will lie in the interior of a side of the dodecagon K. This will also not satisfy the conditions of the extreme case since one of the parallel Figure 5

Figure 6

lines of support for this longest chord will contain only a point of K while the other will contain a segment in K. Thus we have |h^{∗}|/|f(K)| > (2\sqrt{3} + 3)/8, which completes our proof.

Corollary. There exists a number d_{0} < 8(2\sqrt{3} − 3)/3 such that for every convex disk K, there exists a covering of the plane with congruent copies of K, whose density is smaller than or equal to d_{0}.

Proof. Let C be the set of all affine equivalence classes of convex disks. A. M. Macbeath [10] proved that C (and in fact, the n-dimensional analog of C) is a compact metric space. The metrization is accomplished by defining the distance between classes [K] and [L] to be d([K], [L]) = log p(K, L) + log p(L, K) where p(K, L) = inf{|f(L)|/|K|} and f(L) ranges through all convex disks which are affinely equivalent to L and contain K with |K| = 1. Define the function h from C into the non-negative real numbers by assigning to each convex disk K, the ratio between the area of a maximum area p-hexagon contained in K and the area of K. Since the affine image of a p-hexagon is a p-hexagon and ratios of area are preserved under an affine transformation, h is independent of the affine representation chosen for K as it is also continuous over C (see [7] Lemma 3.2 and [8] Lemma 2.2). Therefore h attains its minimum in the compact space C and by the Theorem, this minimum must be smaller than 8(2\sqrt{3} − 3)/3.

References

[1] C. H. Dowker, On minimum circumscribed polygons, Bull. Amer. Math. Soc. 50, 120-122 (1944).

[2] V. Ennola, On the lattice constant of a symmetric convex domain, J. London Math. Soc. 36, 135-138 (1961).

[3] L. Fejes Toth, Lagerungen in der Ebene, auf der Kugel und im Raum (Spinger, Berlin, 1972).

[4] R. Kershner, The number of circles covering a set, American J. Mathematics 61, 665-671 (1939).

[5] G. Kuperberg and W. Kuperberg, Double-lattice packings of convex bodies in the plane, Discrete and Computational Geometry 5, 389-397 (1990).

[6] W. Kuperberg, Packing convex bodies in the plane with density greater than 3/4, Geometriae Dedicata 13, 149-155 (1982).

[7] W. Kuperberg, On packing the plane with congruent copies of a convex body, Intuitive Geom. 48, Janos Bolyai Math. Soc., 317-329 (1985).

[8] W. Kuperberg, An inequality linking packing and covering densities of convex bodies, Geometriae Dedicata 23, 59-66 (1987).

[9] W. Kuperberg, Covering the plane with congruent copies of a convex body, Bull. London Math. Soc. 21, 82-86 (1989).

[10] A. M. Macbeath, A compactness theorem for affine equivalence classes of convex regions, Canadian J. Math. 3, 54-61 (1951).

[11] K. Reinhardt, Uber die dichteste gitterformige Lagerung kongruenter Bereiche in der Ebene und eine besondere Art konvexer Kurven, Abh. math Sem. hansischer Univ. 10, 216-230 (1934).

[12] E. Sas, Uber eine Extremumeigenschaft der Ellipsen,Composito Math. 6, 468-470 (1939).

[13] P. Tammela, An estimate of the critical determinant of a two-dimensional convex symmetric domain (Russian), Izv. Vyss. Ucebn. Zaved. Mat. 12, 103-107, (1970).

[14] A. Thue, Uber die dichteste Zusammenstellung von kongruenten Kreisen in der Ebene, Christinia Vid. Selsk. Skr. 1, 3-9 (1910).

Received 11.10.93