Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 36 (1995), No. 1, 109-117.

On the Lower Bound of Packing Density for Convex Bodies in the Plane

Kevin R. Doheny

Division of Natural Sciences/Mathematics, Dalton College 213 N. College Drive, Dalton, GA 30720-3797,USA

Abstract. G. Kuperberg and W. Kuperberg [12] proved that every convex plane body K admits a packing in the plane with congruent copies of K with density at least \sqrt{3}/2. The author improves on this result by showing that there is a number r_{0} > \sqrt{3}/2 so that if K is a convex plane body, then K admits a packing in the plane by congruent copies of K with density at least r_{0}. The number r_{0} is not shown explicitly.

MSC 1991: 52C15

0. Introduction and Preliminaries

A convex body is a convex, compact set with an interior point. Throughout this paper, K will denote a convex body in the Euclidean plane, and ∂K its boundary. If v is a vector in the plane, r a real number, then v + K denotes the set of points {v + x : x ∈ K}, and rK denotes the set {rx : x ∈ K}. If u and v are independent vectors, then the lattice generated by u and v is the set of vectors {nu + mv : n and m are integers}. The parallelogram spanned by u and v is called a basic parallelogram of the lattice.

A packing with copies of K is a family {K_{i}} of copies of K (i.e., sets congruent to K) whose interiors are mutually disjoint. A lattice packing is a packing in which all elements are translates of each other, and the vectors of translation form a lattice. A double-lattice packing is the union of two lattice packings Q and Q′ such that a 180^{∘} rotation about some point interchanges Q and Q′ (see figures 1 and 2).

The density of a packing P, denoted d(P), is (intuitively) the fraction of the plane covered by P. For arbitrary packings the density is defined in a rigorous way by means of an appropriate limit; in the case of well-behaved packings such as lattice or double-lattice packings, this limit is quite easy to compute. If P is a lattice packing with p the basic parallelogram, then d(P) is |K|/|p|, and if P = Q ∪ Q′ is a double-lattice packing with p

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

Fig. 1. Lattice packing Fig. 2. Double-lattice packing

the basic parallelogram, then d(P) is 2|K|/|p| (where if S is a planar set, then |S| denotes its area).

Among all packings with K, there exists one of maximum density (see Groemer [7]); this is called the packing density of K, denoted δ(K). It is known that if K is centrally symmetric, then the densest packing of K is obtained through a lattice packing; this follows from work by L. Fejes Tóth [4]. Lagrange [13] showed that among all lattice packings with the circular disk B^{2}, the most dense is obtained by circumscribing about B^{2} a regular hexagon, then arranging the hexagons in a lattice so that they tile the plane in the familiar “honeycomb” configuration. Thue [20] showed that among all packings with congruent copies of B^{2}, this same lattice packing was most dense; the density of this packing is π/\sqrt{12}. It is conjectured that if K is centrally symmetric, then δ(K) is at least 0.902414... (see Reinhardt [16] and Mahler [15]). This is the packing density of the “smoothed” octagon, obtained from a regular octagon by “rounding” each corner with the arc of a hyperbola tangent to each of the adjacent sides of the corner, and with asymptotes containing the next adjacent sides. Tammela [19] showed that if K is centrally symmetric, then δ(K) is at least 0.892656...; he obtained this by elaborating on a result by Ennola [2], who suggested the elaboration in his own paper.

A packing in which the copies of K completely cover the plane is called a tiling, and K is called a tile. For an arbitrary convex body K, a natural strategy to find a high density packing is to try to enclose K in some small area polygon P which is a tile, then using a tiling of copies of P to determine a packing with copies of K; the density of such a packing is |K|/|P |. W. Kuperberg [9] used this strategy to show that δ(K) is at least 25/32 for arbitrary K. As already stated in the abstract, the lower bound of the packing density for arbitrary K has been improved upon in [12] using double-lattice packings.

An analogous concept to packings is coverings; a covering with copies of K is a family {K_{i}} of copies of K whose union is the whole plane. The density of a covering C, denoted d(C), is (intuitively) the ratio of the sum of the areas of the covering bodies to that of the space being covered. (A more complete treatment of packing density and covering density, its existence and uniqueness, can be found in L. Fejes Tóth [5], Section III, Chapter 1.) Among all coverings with K, there exists one of minimum density (Groemer [7]); this is called the covering density of K, denoted ϑ(K). Kershner [8] showed that ϑ(B^{2}) = 2π/\sqrt{27}=1.20919...; it is conjectured that every convex body K admits a covering with copies of K with density smaller than or equal to 2π/\sqrt{27}, which is known to be true in case K is centrally symmetric (this follows from the work of Sas [17] and Dowker [1]).

For an arbitrary convex body K, a natural strategy for finding a low density covering is to find some large area polygon P inscribed in K that tiles the plane, then using a tiling of copies of P to determine a covering with copies of K; the density of such a covering is |K|/|P |. W. Kuperberg [11] used this strategy to show that ϑ(K) ≤1.237604... for every K; this was strengthened by Smith [18], who showed that there is a number d_{0} <1.237604... such that every K admits a covering with density at most d_{0}. (The number d_{0} is not shown explicitly.) W. Kuperberg [10] used the combined strategies of inscribed and circumscribed polygonal tiles to prove that δ(K)/ϑ(K) ≥3/4 for arbitrary K. Note that this estimate cannot be improved upon, since equality holds for B^{2}. For a more comprehensive account of the theory of packing and covering, see G. Fejes Tóth and W. Kuperberg [3] and Gritzmann and Wills [6].

A few more details will be needed for the remainder of this work. A chord of K is a line segment in K whose endpoints lie on ∂K. If a and b are points, let \overline{ab} denote the line segment with endpoints a and b. If v is a vector, then the length of K in the direction v is the length of the longest chord of K parallel to v. A chord of K is a diameter of K in the direction of the chord if it is at least as long as any chord parallel to it. A polygon is inscribed in K if all of its vertices lie on ∂K. A vertex w of a polygon is a true vertex if the edges of the polygon that meet at w are not collinear.

1. Extensive Parallelograms

A parallelogram inscribed in K is extensive if each pair of sides is at least half the length of K in the direction parallel to the respective sides (see [12]). If q is an extensive parallelogram inscribed in K, then q can be used to generate a double-lattice packing in the following way: Denote by u and v the vectors spanning q, and suppose one of the vertices of q is situated at the origin. For μ = 0 or 1, let L^{μ} = {2(iu+jv)+(−1)^{μ}K : i, j are integers}. Then L = L^{0} ⋃ L^{1} is a double-lattice packing with copies of K. Note that the density of the double-lattice packing obtained in this manner is |K|/2|q|.

Let v be an arbitrary direction. Suppose d is the length of K in the direction of v, and c_{1} and c_{2} chords parallel to v, each of length d/2; then the parallelogram whose opposite sides are these two chords is called the half-length parallelogram in the direction v. Now, let k_{1} and k_{2} be the lines of support to K parallel to v, w the distance between k_{1} and k_{2}, and e_{1} and e_{2} chords of equal length parallel to v such that the distance between them is w/2; then the parallelogram whose opposite sides are these two chords is called the half-width parallelogram in the direction v. Note that both of these parallelograms, for every direction v, are extensive; the simple proofs are omitted.

The following theorem will be useful:

Theorem. (G. Kuperberg and W. Kuperberg [12]) For every direction v, the area of either the half-length or the half-width parallelogram in the direction v, inscribed in K, is less than or equal to |K|/\sqrt{3}.

It immediately follows then that K admits a double-lattice packing of the plane with density at least \sqrt{3}/2.

2. Raising the Lower Bound On Packing Density

Theorem 1.For every convex plane body K, there exists a direction v such that the area of either the half-length or half-width parallelogram in the direction v, inscribed in K, is smaller than |K|/\sqrt{3}.

Proof. Suppose the opposite; that is, suppose there is a convex plane body K such that for each direction v, the area of each of the half-length and the half-width parallelograms in the direction v, inscribed in K, is at least |K|/\sqrt{3}. Again, by [12], either the half-length or the half-width parallelogram in the direction v has area at most |K|/\sqrt{3}, so equality must hold for one of the two parallelograms in each direction v.

We begin by repeating the basic construction in [12]; in doing this, some conclusions can be drawn and then a contradiction of those conclusions found. Let v be a unit vector in the plane, and let l_{a} and l_{b} be two lines of support to K parallel to v. Find points c and d in K so that \overline{cd} is a diameter of K parallel to v, and let l_{c} and l_{d} be parallel lines of support to K at c and d, respectively. (If more than one diameter of K in the direction v exists, pick the one in the middle.) Consider the parallelogram S determined by l_{a}, l_{b}, l_{c}, and l_{d}; we can assume that S is a square of side length 4 (by a suitable affine transformation, this is possible). Construct, within K, the half-length and half-width parallelograms, L and W, in the direction v. Starting from the point c, label the vertices of L in the clockwise direction, L_{1}, L_{2}, L_{3} and L_{4}. Again, starting from the point c, label the vertices of W in the clockwise direction, W_{1}, W_{2}, W_{3} and W_{4} (see figure 3). Let y be the distance between the sides of L parallel to v, and x the length of the sides of W parallel to v. Note that \overline{cd} does not lie entirely outside of W, and that K contacts both l_{a} and l_{b} at points within the closed strip bounded by the lines containing \overline{L_{1}L_{4}} and \overline{L_{2}L_{3}}.

Fig. 3. The basic construction

Let a, respectively b, be a point of contact of K to l_{a}, respectively to l_{b}, within the closed strip bounded by the lines containing \overline{L_{1}L_{4}} and \overline{L_{2}L_{3}}. Consider the dodecagon D determined by the vertices of the two extensive parallelograms and the points a, b, c, and d; i.e., the points in clockwise order, cW_{1}L_{1}aL_{2}W_{2}dW_{3}L_{3}bL_{4}W_{4} (not all vertices of D need be true vertices). The area of D can be computed by

- combining the areas of the two triangles aL_{1}L_{2} and bL_{4}L_{3}, which is 4 − y

- combining the areas of the two trapezoids L_{1}L_{2}W_{2}W_{1} and W_{4}W_{3}L_{3}L_{4}, which is (x + 2)(y − 2)/2

- combining the areas of the two trapezoids W_{1}W_{2}dc and cdW_{3}W_{4}, which is x + 4. The area of D is the sum of the above amounts, so

(1)  |D| = 6 + (xy/2).

Let t = min(x, y). Then

(2)  |D| = 6 + (xy/2) ≥ 6 + (t^{2}/2);

and, since D ⊂ K, |K| ≥ |D|. Now, if Q is the minimum (in area) of L and W,

|Q| = 2t = |K|/\sqrt{3}, so (3)

t = |K|/2\sqrt{3}. (4)

Then

(5)  |K| ≥ 6 + (|K|^{2}/24),

which has a unique solution |K| = 12. Therefore equality holds, so by (2) and (4) K is the dodecagon D (see figure 4), and t = 2\sqrt{3}. Note, then, that x = y = 2\sqrt{3}. Also, in the above construction, the only restrictions on K being inscribed in the square S, with K having area 12 and S area 16 are

i. K touches each edge of S, and ii. at least one pair of points of contact of K with opposite sides of ∂S are such that the

line segment joining them is parallel to the other two sides of S. Therefore, if K is inscribed in a parallelogram S′ under the two above restrictions, then |K|/|S′| = |K|/|S| = 3/4.

Now, carry out the same construction as above, but with the restrictions that a and b are points in K whose distance is maximum among all points in K, and v is a unit vector in the direction perpendicular to \overline{ab}. Let l_{a}, respectively l_{b}, be the support line to K at a, respectively b, parallel to v. (Note that a, respectively b, is unique as a point of contact of K to l_{a}, respectively l_{b}.) Let l_{c} and l_{d} be parallel lines of support to K perpendicular to l_{a}. Consider the rectangle S determined by l_{a}, l_{b}, l_{c}, and l_{d}; again, we can assume that S is a square of side length 4. Note that K is contained in a parallelogram under the two restrictions given above, so |K| = 12. Denote by \overline{cd} the middle diameter of K parallel to v.

Assertion: \overline{cd} has length 4.

If not, let l and l′ be parallel lines of support to K at c and d, respectively. Note the parallelogram Q determined by l_{a}, l_{b}, l, and l′; K is inscribed in Q under the restrictions listed above, and K has area 12, but Q has area less than 16, a contradiction.

Fig. 4. K is a dodecagon

This means that we can assume c lies on l_{c} and d on l_{d}.

Again, construct within K the half-length and half-width parallelograms, L and W, in the direction v, and label all vertices as above. Then the configuration looks similar to the above, and all conclusions are the same.

Assertion: None of the edges of L and W parallel to v coincide.

The points a and b are unique as points of contact, so the edges of L and W parallel to v do not lie on ∂S. Since the length of the edges of L parallel to v is 2, if one of these edges coincided with an edge of W parallel to v (of length 2\sqrt{3}), then K would not be convex.

Note that K contains the quadrilateral cadb as a proper subset, since the area of this quadrilateral is 8, and the area of K is 12.

Assertion: \overline{ab} is not an edge of S.

Suppose \overline{ab} were an edge of S; then c or d, say c, also would belong to this edge. Consider the triangle determined by a, b, and d; the area of this triangle is 8, so K is not this triangle. Therefore a point p of K lies outside of the triangle, either in the triangle determined by \overline{ad}, l_{d}, and l_{a}, or the triangle determined by \overline{bd}, l_{d}, and l_{b}; assume the former, and assume that p is the furthest such point from \overline{ad}. Let l be the line through p and parallel to \overline{ad}, and l′ the line through b and parallel to l (see figure 5). The quadrilateral S′ determined by l, l′, l_{c}, and l_{d} is a parallelogram containing K satisfying the two properties listed above, but the area of S′ is larger than 16, a contradiction.

Assertion: At least one of the vertices of L is a true vertex of K.

Since K is not the quadrilateral cadb, at least one of the vertices of either L or W is a true vertex of K; assume W contains a true vertex of K. Neither of the two triangles W_{1}W_{2}a and W_{3}W_{4}b is degenerate, since a and b are unique as points of contact (see figure 6); if L doesn’t contain a true vertex of K, then the vertices of L must lie on the edges of

Fig. 5. Changing direction in case \overline{ab} is an edge of K

these two triangles. The combined perpendicular heights of these two triangles is 2, since the distance between \overline{W_{1}W_{2}} and \overline{W_{4}W_{3}} is 2, and the edge length of S is 4. However, the distance between \overline{L_{1}L_{2}} and \overline{L_{4}L_{3}} is 2\sqrt{3}; therefore it is not possible for all vertices of L to lie in the above triangles. Then some vertex of L must lie outside of the two triangles, and so some vertex of L must be a true vertex of K.

Fig. 6. Triangles W_{1}W_{2}a and
W_{4}W_{3}b

Fig. 7. Changing direction in case \overline{ab} is not an edge of K

Suppose the vertex of L that is a true vertex is L_{1} (if not, the following argument would be similar for L_{2}, L_{3}, or L_{4}). Rotate l_{a} about a, slightly toward L_{1} to determine a new line through a, say m_{a}, and rotate l_{b} the same way, to determine a new line through b, say m_{b} (“slightly” meaning so that no other point of K contacts m_{a} or m_{b}). This is possible since a and b are unique as points of contact for K at l_{a} and l_{b}, respectively, and K is a polygon. Consider the parallelogram S′ determined by m_{a}, m_{b}, l_{c}, and l_{d}; S′ has area 16, and K is contained in S′, satisfying conditions i. and ii. above. Now, let e be the chord of K parallel to m_{a} with one endpoint L_{1} (see figure 7). Notice that the edge e is shorter than half the length of the sides of S′ to which e is parallel. By a suitable affine transformation A, turn S′ into a square of side length 4. Let v′ be a unit vector in the direction of A(m_{a}). A(K) is still a dodecagon, and A(L_{1}) is still a true vertex of A(K); however, A(L_{1}) is not a vertex of the new half-length parallelogram L′ inscribed in A(K) in the direction of v′, since A(e) is less than 2. Therefore, the new vertices L′_{1} and L′_{2} of L′ must lie on the side of the line containing A(e) opposite to that on which A(a) lies. But in this new configuration, \overline{L′_{1}A(a)}, and \overline{L′_{2}A(a)} are edges of K; this is a contradiction, since this implies that A(L_{1}) is not in A(K). This completes the proof.

Corollary. Every convex plane body K admits a double-lattice packing of the plane with density greater than \sqrt{3}/2.

Proof. By Theorem 1, there is a direction v such that the area of either the half-length or half-width parallelogram, say q, in the direction v, inscribed in K, is less than |K|/\sqrt{3}. The double-lattice packing P generated by q has density |K|/2|q|, so d(P) = |K|/2|q| > \sqrt{3}/2.

Corollary. There is a number r_{0} > \sqrt{3}/2 such that every convex plane body K admits a double-lattice packing of density greater than or equal to r_{0}.

Proof. Define a function g from the space K of convex bodies, furnished with the Hausdorff metric, to the nonnegative real numbers by g(K) = |K|/2|q|, where q is the minimum area extensive parallelogram inscribed in K. For a given body K, the value of g at K is the maximum double-lattice packing density of K (Sec. 1 and [12]). Note that g is continuous, and has the same value for two affinely equivalent convex bodies. Since the space of affine equivalence classes of convex bodies is compact (see Macbeath [14]), then g attains a minimum. In other words, there exists an element K_{0} in K so that g(K_{0}) is minimum. So, by the corollary to theorem 1, there exists a direction v_{0} and an extensive parallelogram q_{0} inscribed in K_{0} in the direction v_{0} such that |K_{0}|/2|q_{0}| > \sqrt{3}/2. The number r_{0} = g(K_{0}) > \sqrt{3}/2 obviously has the required property.

References

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

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

[3] Fejes Tóth, G. and W. Kuperberg: Packing and Covering with Convex Sets, Chapter 3.3 in Handbook of Convex Geometry, (P. M. Gruber and J. M. Wills, eds.), North-Holland, Amsterdam, 1993, pp. 799 – 860.

[4] Fejes Tóth, L.: Some packing and covering theorems, Acta Sci. Math. (Szeged) 12/A (1950), 62 – 67.

[5] Fejes Tóth, L.: Lagerungen in der Ebene, auf der Kugel und im Raum, 2. Aufl. (Springer, Berlin, 1972).

[6] Gritzmann, P. and J. M. Wills: Finite Packing and Covering, Chapter 3.4 in Handbook of Convex Geometry, (P. M. Gruber and J. M. Wills, eds.) North-Holland, Amsterdam, 1993, pp. 861 – 898.

[7] Groemer, H.: Existenzsätze für Lagerungen im Euklidischen Raum, Math. Z. 81 (1963), 260 – 278.

[8] Kershner, R.: The number of circles covering a set, Amer. J. Math. 61 (1939), 665 – 671.

[9] Kuperberg, W.: On packing the plane with congruent copies of a convex body, Intuitive Geometry, Coll. Janos Bolyai Math. Soc. 48 (1985), 317 – 329.

[10] Kuperberg, W.: An inequality linking packing and covering densities of convex bodies, Geom. Dedicata 23 (1987), 59 – 66.

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

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

[13] Lagrange, J. L.: Recherches d’arithmetique, Nouv. Mem. Acad. Roy. Sci. Belles Lettres Berlin, 265 – 312 [Oeuvres, Vol. III (Gauthier-Villars, Paris, 1869) pp. 693 – 758].

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

[15] Mahler, K.: On the minimum determinant and the circumscribed hexagons of a convex domain, Nederl. Akad. Wetensch. Proc. Ser. A 50 (1947), 692 – 703.

[16] Reinhardt, K.: Über die dichteste gitterförmige Lagerung kongruenter Bereiche in der Ebene und eine besondere Art konvexer Kurven, Abh. Math. Sem. Hansischer Univ. 10 (1934), 216 – 230.

[17] Sas, E.: Über eine Extremumeigenschaft der Ellipsen, Compisitio Math. 6 (1939), 468 – 470.

[18] Smith, E.: Covering the plane with congruent copies of a convex disk, Beitr. Algebra Geom. 35 (1994), 101 – 108.

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

[20] Thue, A.: Über die dichteste Zusammenstellung von kongruenten Kreisen in der Ebene, Norske Vid. Selsk. Skr. 1 (1910), 1 – 9.

Received September 26, 1994.