Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 43 (2002), No. 2, 501-511.

On Minimum Kissing Numbers of Finite Translative Packings of a Convex Body

István Talata^{1}

Department of Mathematics, Auburn University 218 Parker Hall, Auburn, AL 36849-5310, USA^{2} e-mail: talata@math.lsa.umich.edu

Abstract. For a convex body K, let us denote by t(K) the largest number for which there exists a packing with finitely many translates of K in which every translate has at least t(K) neighbours. In this paper we determine t(K) for convex discs and 3-dimensional convex cylinders. We also examine how small the cardinalities of the extremal configurations can be in these cases. MSC 2000: 52C17, 52A10 Keywords: convex cylinder, convex disc, kissing number, translative packing

1. Introduction

In this paper we consider the problem how large the minimum number of neighbours of a member can be in a packing with finitely many translates of a convex body. A related result of Kertész [6] shows that in any finite packing of ℝ^{3} with congruent balls there is a member having at most eight neighbours. It is not known if eight can be replaced by seven or six in the previous statement. On the other hand, in higher dimensions Alon [1] constructed finite packings of equal balls in which every member has a large number of neighbours (namely, at least 2^{\sqrt{d}} neighbours for every dimension d = 4^{k}, k ∈ ℕ).

First we give a solution of the problem for convex discs, then for 3-dimensional convex cylinders. (By a convex cylinder we mean a convex body which is the Minkowski sum of a segment and a compact convex set of dimension smaller by one.) We also investigate on the minimum cardinalities of the extremal packings for these convex bodies. Note that Österreicher and Linhart [8] examined similar problems in ℝ^{2} for packings with congruent copies of smooth convex discs. For additional related results and references in this topic, see the survey papers by G. Fejes Tóth [2] and by G. Fejes Tóth and W. Kuperberg [3].

1 The work was partially supported by the Hungarian National Science Foundation, grant no.

A-221/95

2 Current address: Department of Mathematics, The University of Michigan, East Hall, 525 East University Avenue, Ann Arbor, MI 48109-1109, USA 0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}2002 Heldermann Verlag

Let us recall some notions. By a translative packing of a convex body we mean a collection of mutually nonoverlapping translates of that body. The neighbours of a member K′ in a packing are those members that have a common point with K′ and are different from K′ (i.e. they touch K′). The kissing numbers of a packing are the numbers occuring as the number of neighbours of some member in the packing. The minimum kissing number of a packing is the least among all kissing numbers of the packing, that is, it is the minimum number of neighbours that a member has in the packing. A 2-dimensional convex body is called a convex disc.

For a given convex body K, let t(K) denote the largest number for which there is a packing with finitely many translates of K in which every member has at least t(K) neighbours. In other words, t(K) is the maximum of the minimum kissing numbers of packings with finitely many translates of K. Let m(K) be the minimum cardinality of packings with finitely many translates of K whose minimum kissing numbers are maximal, i.e. equal to t(K).

We prove the following two theorems.

Theorem 1. Let D be a convex disc. Then

t(D) = \{ \begin{matrix}3, & if D is not a parallelogram, \\ 4, & if D is a parallelogram, \end{matrix}

and

m(D) = \{ \begin{matrix}7, & if D is not a parallelogram, \\ 12, & if D is a parallelogram. \end{matrix}

Theorem 2. Let C be a 3-dimensional convex cylinder. Then

t(C) = \{ \begin{matrix}10, & if D is not a parallelepiped, \\ 13, & if D is a parallelepiped, \end{matrix}

and

m(C) ≤ \{ \begin{matrix}172, & if D is not a parallelepiped \\ 392, & if D is a parallelepiped. \end{matrix}

One can reformulate the problem considered in this paper in terms of Minkowski spaces. (By a Minkowski space we mean a finite dimensional normed space in this paper.) Recall that two translates of a d-dimensional convex body K are nonoverlapping [resp., touching] exactly if the distance between their translation vectors is at least 1 [resp., exactly 1] in ℝ^{d} equipped with the Minkowski metric whose unit ball is the difference body of K. Using this property, it is easy to see that the problem is equivalent to the following: In a given Minkowski space, how large the minimum vertex degree of a graph can be in which the vertices are formed by finitely many distinct points of the space and two vertices are connected by an edge exactly if the distance between them is minimal, that is, it is equal to the minimum distance occuring between any two vertices of the graph? By Theorems 1 and 2 this problem is solved when the Minkowski space is either 2-dimensional or it is 3-dimensional and has a cylindrical unit ball.

2. Proof of Theorem 1

First we recall some notations. We use the standard notation αA+βB for the set {αa+βb ∈ ℝ^{d} | a ∈ A, b ∈ B} for arbitrary A, B ⊆ ℝ^{d} and α, β ∈ ℝ. If v ∈ ℝ^{d}, then we simply write A + v instead of A + {v}, and we write A − B instead of A + (−1)B. If U ⊆ ℝ^{d} and V is a collection of subsets of ℝ^{d}, then we introduce the notation U(∩)V = {U ∩ V | V ∈ V}. For a convex body K, we denote its boundary by ∂K. If F is a finite set, then we denote its cardinality by |F |.

We now recall a well-known observation of Minkowski [7], which says that two translates K + x and K + y of a convex body K have a common point if and only if the two translates \frac{1}{2}(K − K) + x and \frac{1}{2}(K − K) + y of the Minkowski symmetrization \frac{1}{2}(K − K) of K have a common point. This shows that it suffices to prove Theorem 1 when D is centrally symmetric. Therefore we may assume throughout the proof that D is centrally symmetric.

Let P be an arbitrary packing with finitely many translates of D, and let S = conv(⋃ P), where conv(.) stands for the convex hull of a set. We distinguish two cases.

Case 1. D is a parallelogram. By affine invariance it is enough to consider the case D = [0, 1]^{2} ⊆ ℝ^{2}.

Consider a supporting line l_{1} of S which is horizontal (i.e. parallel to the first coordinate axis). Then l_{1}(∩)P is a nonempty collection of finitely many nonoverlapping segments lying in l_{1}. Let D_{1} ∈ P be chosen so that l_{1} ∩ D_{1} ≠ ∅ and l_{1} ∩ D_{1} does not separate any other two segments of l_{1}(∩)P in l_{1}. Let l′_{1} ≠ l_{1} be the other line parallel to l_{1} which contains a side of D_{1}. Since it is clear that at most one neighbour of D_{1} intersects l_{1}, there are at most three neighbours of D_{1} which intersect l′_{1} and do not intersect l_{1}, and that every neighbour of D_{1} intersects either l_{1} or l′_{1}, thus we get that D_{1} has at most four neighbours. This shows t(D) ≤ 4.

Now, consider an n × n grid of translates of D for n ≥ 4, and remove the four translates of D at the corners of the grid. In this finite packing every member has at least four neighbours (the case n = 4 is illustrated in Figure 1). This implies t(D) ≥ 4. Consequently t(D) = 4.

Assume now that in P every member has at least four neighbours. Then we get that exactly one neighbour of D_{1} intersects l_{1}, and there are exactly three neighbours of D_{1} which intersect l′_{1} and do not intersect l_{1}. But for a fixed supporting line l_{1} of S there are two distinct choices D_{11} and D_{12} for D_{1}, and they have at most two common neighbours. Thus there are at least six members of P which have a neighbour intersecting l_{1}. On the other hand, it is also implied that the horizontal width of S (i.e. the length of the projection of S to the horizontal coordinate axis) is at least 4.

Let l_{2} ≠ l_{1} be the other horizontal supporting line of S. An analogous argument shows that there are at least six members of P which have a neighbour intersecting l_{2}.

Figure 1. A translative packing of 12 squares with minimum kissing number 4

Now, considering the vertical supporting lines of S, the very same kind of argument as in the horizontal case gives that the vertical width of S is at least 4. Therefore those two subcollections of P formed by those members of P which have neighbours intersecting l_{1} and l_{2}, respectively, have no common members. Since each subcollection has at least six elements, we get |P| ≥ 12. Therefore m(D) ≥ 12.

On the other hand, in the above mentioned example derived from the n × n grid there are 12 translates of D for n = 4. This implies m(D) ≤ 12. Consequently m(D) = 12.

Case 2. D is not a parallelogram. First we prove t(D) ≤ 3. We begin with introducing some notions. A packing H of translates of D is a Hadwiger configuration if every member of the packing touches D. Two members D_{1}, D_{2} ∈ H are called opposite if the center of D is the midpoint of the segment connecting the centers of D_{1} and D_{2} (recall that D is centrally symmetric throughout the proof). Note that a Hadwiger configuration has a natural cyclic order. We say that there is a gap in a Hadwiger configuration H if there are two consecutive members of H which are disjoint. A segment s connecting two points of a convex disc D is a long segment if its length is larger than the half of the maximum length of chords of D parallel to s.

Subcase 1. ∂D does not contain two nonoverlapping long segments having a common endpoint. In this case, by Swanepoel [9] either every Hadwiger configuration of six translates of D consists of three pairs of opposite members or it contains a pair of opposite translates with translational vectors parallel to a long segment of ∂D.

If ∂D contains a long segment, then let l be a supporting line of S parallel to one such long segment. Otherwise choose an arbitrary supporting line of S as l. Let D_{1} ∈ P be chosen so that l ∩ D_{1} ≠ ∅ and l ∩ D_{1} does not separate any other two members of l(∩)P in l.

We now assume the contrary, i.e. t(D) ≥ 4. Then we may assume that there are at least four neighbours of D_{1} in P. Since l is a supporting line of both D_{1} and S, it can be easily shown that there are two translates D′ and D′′ of D with D′, D′′ ∉ P which do not overlap any neighbour of D_{1} in P and touch D_{1}. These two translates and the neighbours of D_{1} form a Hadwiger configuration of at least six translates of D_{1}. But then by the fact that in a planar packing with translates of a convex disc every member has at most six neighbours if the disc is different from a parallelogram (see Grünbaum [5]), there are exactly six members in this new configuration. We may choose D′ and D′′ to be non-opposite to any neighbour of D_{1} in P (in fact, we can choose D′ and D′′ so that the line determined by their centers encloses any sufficiently small nonzero angle with l). This implies that there must be two opposite translates among the neighbours of D_{1} in P, contradicting that l ∩ D_{1} does not separate any other two members of l(∩)P in l.

Subcase 2. ∂D contains two nonoverlapping long segments having a common endpoint. In this case it can be easily seen that there exists an affine transformation f : ℝ^{2} → ℝ^{2} for which V ⊆ f(D) ⊆ [−1, 1]^{2}, where V is the union of the midpoints of the sides of the square [−1, 1]^{2} and its two vertices (−1, 1) and (1, −1).

Let D′ = f(D), P′ = {(P), and S′ = f(S). Consider a horizontal supporting line l of S′, and a member D′_{1} ∈ P′ chosen so that l ∩ D′_{1} does not separate any other two segments of l(∩)P′ in l. Without loss of generality we may assume that l = {(x_{1}, x_{2}) ∈ ℝ^{2} | x_{2} = 1}, D′_{1} = D′, and l′(∩)P′ = ∅ for l′ = l ∩ H^{−}, where H^{−} = {(x_{1}, x_{2}) ∈ ℝ^{2} | x_{1} < −1}.

For every k ∈ ℝ, let H_{k}^{+} be the closed halfplane defined as

H_{k}^{+} = {(x_{1}, x_{2}) ∈ ℝ^{2} | x_{1} ≥ k}.

Let s be the half-open segment

s = {(x, −1) ∈ ℝ^{2} | −1 ≤ x < 1}.

We also introduce notations for some translates of D′:

\begin{aligned}D′_{k} & = D′ + (k − 1, 0), \\ D′′_{k} & = D′ + (k − 1, −2). \end{aligned}

Let us assume the contrary, i.e. every member of P has at least four neighbours. Then the same holds for every member of P′ as well. It is clear that H_{1}^{+} contains at most two neighbours of D′_{1} in P′, and if it contains exactly two neighbours, then these are D′_{3} and D′′_{3}. It is also easy to see that at most two neighbours of D′_{1} intersect s. On the other hand, any neighbour of D′_{1} either is contained in H_{1}^{+} or intersects s. Therefore, since D′_{1} has at least four neighbours by assumption, we get that D′_{1} has exactly four neighbours in P′ and D′_{3}, D′′_{3}, D′′_{1} are among them. Now we consider the neighbours of D′_{3}: there are exactly two which are not contained in H_{3}^{+}. Thus there must be exactly two, D′_{5} and D′′_{5} contained in H_{3}^{+}. Repeating similar arguments for D′_{i} with i = 5, 7, 9, …, we obtain by induction that D′_{i} and D′′_{i} are members of P for every positive odd number i. But this contradicts the finiteness of P. Consequently, we get t(D) ≤ 3.

Next we show t(D) ≥ 3. We may assume that D is symmetric about the origin o ∈ ℝ^{2}. Let us consider the packing of six translates of D with centers of the vertices of an affine regular hexagon inscribed into 2D (for the existence of such a hexagon, see [4]). Then

Figure 2. A translative packing of 7 circles with minimum kissing number 3

these six translates form a Hadwiger configuration of D with no gap. This means that these six translates and D form a packing of seven translates of D in which every member has at least three neighbours (Figure 2 shows the case when D is a circle). Consequently t(D) ≥ 3. This example also shows that m(D) ≤ 7.

It remains to prove that m(D) ≥ 7. First we introduce a notion and notations. Then we prove a lemma and its corollary which are needed for the proof of the lower bound.

Let K be a centrally symmetric convex body. By the relative length of a segment s ⊆ ℝ^{2} with respect to K we mean the ratio of the usual (Euclidean) length of s and the half of the usual length of the longest chord of K parallel to s. For a, b ∈ ℝ^{2}, we write ab for the segment with endpoints a and b. We introduce the notation (ab)_{K} for the relative length of the segment ab. Observe that ab ⊆ K is a long segment if and only if (ab)_{K} > 1. Note that the introduced notion of relative length coincides with the Minkowski metric in which the unit ball is K. If x = (x_{1}, x_{2}) ∈ ℝ^{2}, then let π_{i}(x) = x_{i} for i = 1, 2.

Lemma 1. Let K be a centrally symmetric convex disc different from a parallelogram. Then any pentagon inscribed into K and containing the center of K has a side which is a long segment in K.

Corollary 2. Let K be a centrally symmetric convex disc different from a parallelogram. Then there is a gap in every Hadwiger configuration of n translates of K for any 3 ≤ n ≤ 5.

Proof of Lemma 1. Consider an arbitrary pentagon inscribed into K which contains the center of K, and has consecutive vertices p_{1}, p_{2}, …, p_{5} ordered counterclockwise.

First assume that ∂K does not contain a long segment. In this case it is easy to see that we have (ab)_{K} < (ac)_{K} for any three distinct consecutive points a, b, c ∈ ∂K when b is contained in the shorter component of ∂K \ {a, c} (cf. Lemma 2 of [9]). Let H be an affine regular hexagon inscribed into K having the same center as K. For the existence of such a hexagon, see [4]. It is clear that all sides of H have relative length 1 with respect to K. Consider a partition of ∂K into five disjoint half-open arcs A_{i} connecting p_{i} and p_{i+1}, and not containing p_{i+1}, 1 ≤ i ≤ 5 (using the notation p_{6} = p_{1}). Then there are two consecutive vertices q, q′ of H which are contained in one of these half-open arcs, say, in A_{1}. We may assume that p_{1}, q, q′, p_{2} are consecutive points of ∂K with q′ ≠ p_{2} but allowing q = p_{1}. Then 1 = (qq′)_{K} ≤ (p_{1}q′)_{K} < (p_{1}p_{2})_{K}. Therefore p_{1}p_{2} is a long segment in K.

Secondly, assume that ∂K contains a long segment. Then, by central symmetry, ∂K contains two parallel long segments of equal length. Without loss of generality we may assume that s_{1} = E_{1} ∩ K and s_{−1} = E_{−1} ∩ K are long segments in K, and s_{1}, s_{−1} are the vertical sides of the square [−1, 1]^{2}, where E_{r} is the vertical line E_{r} = {(x_{1}, x_{2}) | x_{1} = r} (r ∈ ℝ).

Assume the contrary, i.e. (p_{i}p_{i+1})_{K} ≤ 1 for every 1 ≤ i ≤ 5. Then it is clear that p_{l} ∈ s_{1} and p_{k} ∈ s_{−1} for some not cyclically consecutive l and k. We may assume that l = 1 and k = 3. Then it can be seen that π_{1}(p_{2}) = 0, which implies π_{2}(p_{i}) > 0 for i = 1, 3. But from this follows that π_{1}(p_{5}) − π_{1}(p_{4}) > 1. However, this means that (p_{4}p_{5})_{K} > 1, which is a contradiction. □

Proof of Corollary 2. Consider the centers of the translates in the Hadwiger configuration. They form the vertices of a polygon P inscribed into ∂K′, where K′ is a homothetic copy of K enlarged from the center of K by coefficient 2. Assume the contrary, that is, there is no gap in the Hadwiger configuration. Then each side of P has relative length 1 with respect to K′. This clearly implies that the center of K′ is contained in P. Consider a pentagon P′ inscribed into K′ whose vertices contain the vertices of P. Then every side of P′ has relative length at most 1 with respect to K′, contradicting Lemma 1. □

We now continue the proof of Theorem 1. We prove m(D) ≥ 7. Assume the contrary, that is, there exists a packing P of at most six translates of D in which every member has at least three neighbours.

First observe that since D is not a parallelogram, therefore in a Hadwiger configuration of D at most two consecutive members can have a common point. By Corollary 2, this implies that any member of P can have at most four neighbours. On the other hand, two disjoint members of P can have at most two common neighbours, otherwise D has to be a parallelogram, a contradiction (cf. Lemma 1 of [9]). This last observation, together with Corollary 2, implies that for any D′ ∈ P, D′ has exactly three neighbours, and there are exactly two members of P which are disjoint from D′, and these two members must be touching. In particular, this shows |P| = 6.

Let the three neighbours of a member D_{1} ∈ P be D_{2}, D_{3} and D_{4}. Then D_{5}, D_{6} ∈ P are touching, each of them having two neighbours from N_{1} = {D_{2}, D_{3}, D_{4}}. This means that one of the members of N_{1}, say D_{3} touches both D_{5} and D_{6}. Since then D_{1}, D_{5}, D_{6} are neighbours of D_{3}, this implies that D_{2} and D_{4} are neighbours but both are disjoint from D_{3}. Moreover, D_{2} must touch exactly one of the members D_{5}, D_{6}, say D_{6}. Then D_{4} touches D_{5} but disjoint from D_{6}.

Let q_{i} be the center of D_{i} (1 ≤ i ≤ 6). We may assume that D_{1} = D and q_{1} = o, where o is the origin of ℝ^{2}. Let q′_{5} = q_{1}q_{5} ∩∂(2D), and q′_{6} = q_{1}q_{6} ∩∂(2D). Since (q_{1}q_{4})_{2D} = (q_{5}q_{4})_{2D} = 1, therefore we have (q′_{5}q_{4})_{2D} ≤ 1. It can be obtained similarly that (q′_{5}q_{3})_{2D} ≤ 1, (q′_{6}q_{2})_{2D} ≤ 1, and (q′_{6}q_{3})_{2D} ≤ 1. From (q_{2}q_{4})_{2D} = 1 follows that q_{3}, q′_{5}, q_{4}, q_{2}, q′_{6} form the vertices of a pentagon inscribed into 2D with every side having relative length at most 1. On the other hand, o is in the bounded region enclosed by the consecutively touching members D_{3}, D_{5}, D_{4}, D_{2}, D_{6}, therefore it is in the closed pentagon q_{3}, q_{5}, q_{4}, q_{2}, q_{6}, and by the definition of q′_{i}, i = 5, 6, o is inside of the pentagon q_{3}, q′_{5}, q_{4}, q_{2}, q′_{6}, too. But this contradicts Lemma 1. This completes the proof of Theorem 1. □

3. Proof of Theorem 2

Similarly to the proof of Theorem 1, we may assume that C is centrally symmetric. Moreover, by affine invariance, we may also assume that C = D ×[−1, 1], where D is a centrally symmetric convex disc.

We introduce two kind of maps. Let π : ℝ^{3} → ℝ^{2} be defined as π(x_{1}, x_{2}, x_{3}) = (x_{1}, x_{2}), and for any r ∈ ℝ let f_{r} : ℝ^{2} → ℝ^{3} be defined as f_{r}(x_{1}, x_{2}) = (x_{1}, x_{2}, r). Let H be the x_{1}x_{2}-plane, that is H = f_{0}(ℝ^{2}).

First we prove that t(C) ≤ 13 if C is a parallelepiped, and that t(C) ≤ 10 otherwise. Let C be a packing of finitely many translates of C. Consider a supporting plane H′ of conv(⋃ C) parallel to H. Let

P = {π(C′) | C′ ∩ H′ ≠ ∅, C′ ∈ C}.

Then P is a planar packing of finitely many translates of D, so it has a member π(C_{1}), where C_{1} ∈ C, which has at most t(D) neighbours. Denote by H(D) the Hadwiger number of D which is defined as the maximum cardinality of the Hadwiger configurations of translates of D.

Let H′′ be a supporting plane of C_{1} parallel to H and different from H′. Then clearly, there are at most H(D) + 1 neighbours of C_{1} in C which intersect H′′ but do not intersect H′. Since every neighbour of C_{1} in C intersects either H′ or H′′, we get that t(C) ≤ t(D) + H(D) + 1. On the other hand, C is a parallelepiped if and only if D is a parallelogram. We also know by Theorem 1 and by [5] that t(D) = 4 and H(D) = 8 for parallelograms, while t(D) = 3 and H(D) = 6 otherwise. These facts together imply t(C) ≤ 13 if C is a parallelepiped, and t(C) ≤ 10 otherwise.

In the remaining part of the proof we give constructions for packings with finitely many translates of the cylinder C where every member has at least t(C) neighbours. These constructions complete the proof of Theorem 2. In the description of the constructions we use the notation vert(A) for the vertex set of a convex polygon or convex polyhedron A. We distinguish two cases.

Case 1. C is a parallelepiped.

We may assume that C = [−1, 1]^{3}. We construct a packing of 392 translates of C where every member has at least 13 neighbours. An outside view of the packing is shown in Figure 3 (note that the figure does not show that there is a “hole” inside). Clearly, it is enough to construct a set S ⊆ ℤ^{3} of translation vectors of C containing only odd coordinates, since then {C} + S gives a packing.

Then the only remainig task is to check that every member in this packing has at least 13 neighbours. This becomes relatively easy, because of the highly symmetric structure of the packing there are only few cases to check.

Here is the construction. Let 𝕆 = 2ℤ + 1, and

\begin{aligned}B_{1} & = ([−5, 5]^{2} \ vert([−5, 5]^{2})) ∩ 𝕆^{2}, \\ B_{2} & = ([−3, 3]^{2} \ vert([−3, 3]^{2})) ∩ 𝕆^{2}, \end{aligned}

\begin{aligned}B_{3} & = ([−1, 1]^{2} ∩ 𝕆^{2}, \\ S_{1} & = [−5, 5]^{3} ∩ 𝕆^{3}, \\ S_{2} & = f_{7}(B_{1}) ∪ f_{−7}(B_{1}), \\ S_{3} & = f_{9}(B_{2}) ∪ f_{−9}(B_{2}), \\ I_{1} & = [−3, 3]^{3} ∩ 𝕆^{3}, \\ I_{2} & = f_{5}(B_{3}) ∪ f_{−5}(B_{3}). \end{aligned}

Let S′ = S_{1} ∪S_{2} ∪S_{3}, I′ = I_{1} ∪I_{2}. Let S′′ and I′′ be the set of all coordinate permutations of the points of S′ and I′, respectively. Let us define S = S′′\I′′. Then {C}+S is a packing with 392 translates of C. By symmetry it suffices to check that those members have at least 13 neighbours whose translation vectors are the following: (1, 1, 9), (1, 3, 9), (1, 1, 7), (1, k, 7), (3, k, 7), (1, k, 5), (3, k, 5), (5, 5, 5), for k = 3 and 5. We leave this verification to the reader.

More visually (but less precisely), the construction can be described in this way: Consider [−6, 6]^{3} formed by 6^{3} = 216 translates of C = [−1, 1]^{3}. Then consider a 6 × 6 × 1 grid of C without the 4 cubes at the corners, and put its copies, as “caps” onto the faces of the cube [−6, 6]^{3}. This gives additionally 6(6^{2} − 4) = 192 cubes. Now, consider a 4 × 4 × 1 grid of C without the 4 cubes at the corners, and place its copies, as “caps”, “in the middle” of the top of the previously placed larger “caps”. This gives additionally 6(4^{2}−4) = 72 cubes. Finally, from the middle of the packing remove the union of a 4×4×4 cubic grid and six 2 × 2 × 1 “caps” of cubes placed on the middle of the top of the faces of the cube formed by the 4 × 4 × 4 grid. Thus the total number of cubes in the packing is 216 + 192 + 72 − 64 − 24 = 392.

Figure 3. A translative packing of 392 cubes with minimum kissing number 13

Case 2. C is not a parallelepiped.

Consider an affine regular hexagon H inscribed into D. Without loss of generality we may assume that H is a regular hexagon centered in the origin o ∈ ℝ^{2} and with consecutive vertices v and w. Then the planar lattice L spanned by 2v and 2w induces a lattice packing {D} + L where every member has exactly 6 neighbours.

Now, the construction is the following. Let

\begin{aligned}Z_{1} & = f_{7}(2H ∩ L) ∪ f_{−7}(2H ∩ L), \\ Z_{2} & = f_{5}(4H ∩ L) ∪ f_{−5}(4H ∩ L), \\ Z_{3} & = f_{3}((6H \ vert(6H)) ∩ (L \ \{o\})) ∪ f_{−3}((6H \ vert(6H)) ∩ (L \ \{o\})), \\ Z_{4} & = f_{1}((6H \ (2H)) ∩ L) ∪ f_{−1}((6H \ (2H)) ∩ L). \end{aligned}

Let Z = ⋃_{i=1}^{4} Z_{i}. Then {C} + Z is a packing with 172 translates of C. An outside view of the packing is shown in Figure 4 in the case when the base of the cylinder is a regular hexagon (note that the figure does not show that there is a “hole” inside). To prove that every member has at least 10 neighbours, by the high symmetry it suffices to check this property for those members whose translation vectors are the following: f_{7}(o), f_{7}(2v), f_{5}(o), f_{5}(2kv), f_{5}(2v + 2w), f_{3}(2kv), f_{3}(2kv + 2w), f_{1}(2(k + 1)v), f_{1}(2kv + 2w), for k = 1 and 2. We leave this verification to the reader. This completes the proof of Theorem 2. □

Figure 4. A translative packing of 172 hexagonal cylinders with minimum kissing number 10

4. Concluding remarks

When D is a parallelogram, then from the proof of m(D) = 12 in Section 2 one can derive without much effort that the configuration obtained from the 4×4 grid of D by leaving the four translates at the corners is an essentially unique example for a packing with twelve translates of D where every member has at least four neighbours. (By essential uniqueness we mean that a configuration is unique up to simultaneous translations.)

Using similar methods as in the proof of the upper bounds for t(C) in Section 3, it can be easily seen that t(P_{d}) ≤ (3^{d} − 1)/2 for any d-dimensional paralleletope P_{d}, and t(D × [0, 1]^{d−2}) ≤ 3 + 7(3^{d−2} − 1)/2 for any convex disc D and d ≥ 2.

It seems very likely that the value of m(C) is relatively large for 3-dimensional convex cylinders, let us say larger than 100. Currently we do not any extremal configurations for 3-dimensional convex cylinders with smaller number of translates than the above described ones with 392 and 172 translates for parallelepipeds and other 3-dimensional convex cylinders, respectively.

Acknowledgements. For the helpful discussions and encouragement, I am obliged to Gábor Fejes Tóth.

References

[1] Alon, N.: Packings with large minimum kissing numbers. Discrete Math. 175 (1997), 249–251. Zbl 0894.52008

[2] Fejes Tóth, G.: Packing and covering. In: Handbook of Discrete and Computational Geometry, ed. by J. E. Goodman and J. O’Rourke, CRC Press, Boca Raton, New York 1997, 19–41. Zbl 0924.52007

[3] Fejes Tóth, G.; Kuperberg, W.: A survey of recent results in the theory of packing and covering. In: New trends in discrete and computational geometry, ed. by J. Pach, Springer-Verlag Berlin-Heidelberg-New York 1993, 251–279. Zbl 0798.52020

[4] Fejes Tóth, L.: Lagerungen in der Ebene, auf der Kugel und im Raum. Springer-Verlag Berlin 1953. Zbl 0052.18401

[5] Grünbaum, B.: On a conjecture of H. Hadwiger. Pacific J. Math. 11 (1961), 215–219. Zbl 0131.20003

[6] Kertész, G.: Nine points on the hemisphere. Colloq. Math. Soc. J. Bolyai (Intuitive Geometry, Szeged 1991) 63 (1994), 189–196. Zbl 0822.52005

[7] Minkowski, H.: Dichteste gitterförmige Lagerung kongruenter Körper. Nachr. Ges. Wiss. Göttingen 1904, 311–355.

[8] Österreicher, F.; Linhart, J.: Packungen kongruenter Stäbchen mit konstanter Nachbarnzahl. Elem. Math. 37 (1981), 5–16. Zbl 0468.52010

[9] Swanepoel, K. J.: Gaps in convex disc packings with an application to 1-Steiner minimum trees. Monatsh. Math. 129 (2000), 217–226. Zbl 0957.52001

Received June 14, 1999; revised version December 12, 2001