Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 41 (2000), No. 2, 329-334.

On Parametric Density of Finite Circle Packings

Achill Schürmann

Fachbereich Mathematik, Universität Siegen Postfach 101240, D-57068 Siegen 21, Germany

Abstract. The parametric density of a finite circle packing X_{n} + D is defined as ratio of areas n · A(D)/A (conv(X_{n} + ρD)). We show that densest finite lattice packings are attained in a critical lattice. Further, we give an upper bound for the density with parameters ρ ≤ 3.232 … which is attained by Groemerpackings. Moreover, we show that the given bound holds for arbitrary finite circle packings and parameters less than 1 as a consequence of known results by H. Groemer [5] and G. Wegner [11].

1. Introduction

We call a non-overlapping arrangement of a finite number of congruent discs a finite circle packing. As an example, we may think of the cross-section of a multi-core (e.g. optical fibers) cable, enclosed by some type of insulation (cf. Figure 1). Problem: How can one pack a fixed number of cores to minimize the area of such a cross-section; or: what is the maximal parametric density of such a circle packing?

The answer depends on the parameter defined thickness of the used insulation. With infinitely small insulation the cross-section is the convex hull of the packing, which has been investigated in many papers (cf. [3]). The best known results were given by Groemer [5] (Theorem 3.1) and Wegner [11] (Theorem 3.2). Their bounds hold with equality only for Groemerpackings (see Theorem 3.1). In these packings the disc-centers belong to a ‘critical lattice’.

We show that for any parameter the highest parametric density of a lattice packing is attained if and only if the lattice is critical (Theorem 3.3). It turns out that ‘extremal

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

Groemerpackings’ (see Theorem 3.2) which minimize the convex hull are best possible lattice packings for all parameters in [\frac{\sqrt{3}}{2}, \frac{3}{2} + \sqrt{3}] (Theorem 3.4). This shows that cable-cross-

sections become minimal when the thickness of the insulation is less than (\frac{1}{2} + \sqrt{3})-times the disc-radii.

2. Notation and simplification

Let 𝔼^{2} denote the Euclidian plane with norm ∥·∥, inner product ⟨·, ·⟩ and unit disc D. A finite set X_{n} = {x_{1}, …, x_{n}} ⊂ 𝔼^{2} defines a finite circle packing X_{n} + D when ∥x − x′∥ ≥ 2 holds for all pairs of distinct points x, x′ ∈ X. The (parametric) density of the packing (cf. [1]) with respect to a parameter ρ > 0 is given by

δ (D, X_{n}, ρ) = \frac{n · π}{A (conv(X_{n} + ρD))} .  (1)

Figure 1.

Here, A denotes the area function, and conv(·) denotes the convex hull. In order to maximize the density of n discs, we have to minimize the denominator. With Steiner’s Formula (cf. [6]) we get

A (conv(X_{n} + ρD)) = A (conv(X_{n})) + ρ · C (conv(X_{n})) + ρ^{2} · π,

where C evaluates the circumference of the center-polygon P = conv(X_{n}). Figure 1 shows a geometrical interpretation of the three summands in Steiner’s Formula. Since we want to find densest packings for a fixed parameter ρ, we have to minimize the linear function

F_{P} (ρ) = A(P) + ρ · C(P) over P(n) = {P | P = conv(X_{n}), X_{n} + D packing} .

Hence, any lower bound for F_{P} (ρ) yields an upper bound for the parametric density of the densest packing with n translates of D.

A lattice Λ is called a packing lattice when Λ + D is a packing. Λ is called critical if and only if every disc in Λ + D touches six others. We call P = conv(X_{n}) a Λ-polygon if X_{n} is a subset of Λ, and a critical lattice polygon, if Λ is critical. The number of lattice points covered by P is denoted by G_{Λ}(P). A segment [AB] ⊂ bd(P) is called an edge of P when it satisfies [AB]∩X_{n} = {A, B}. Its length is given by |AB|. The number of edges is denoted by E_{Λ}(P), where edges are counted twice for degenerated polygons (‘sausages’). Fundamental for the work with lattice polygons is Pick’s Identity (cf. [4])

G_{Λ}(P) = \frac{A(P)}{det(Λ)} + \frac{E_{Λ}(P)}{2} + 1,

where det(Λ) denotes the determinant (area of a fundamental cell) of Λ (cf. [6]).

We only investigate lattice polygons in order to find densest lattice packings. This is sufficient, since a densest lattice packing, has to be saturated (P ∩ Λ = X_{n}). Otherwise we could construct a new and denser packing by replacing a vertex of P in X_{n} with another lattice point.

3. Results

First we are going to use the introduced notation to state the known results by H. Groemer and G. Wegner. We then put those results into a wider context.

Theorem 3.1. (Groemer) For n ∈ ℕ, ρ = \frac{\sqrt{3}}{2} and P ∈ P(n) holds

F_{P} (ρ) ≥ (n − 1) 2\sqrt{3}.

Equality holds if and only if P is a Groemerpolygon. That is a (possibly degenerated) critical lattice polygon with all edges having length 2. The corresponding saturated circle packing is called a Groemerpacking.

An elegant proof was given by Graham, Witsenhausen and Zassenhaus [2], who generalized a result by Oler [7]. This proof also takes arbitrary centrally symmetric discs into consideration. The other classical result on finite circle packings is given by

Theorem 3.2. (Wegner) For n ∈ ℕ, ρ = 1 and P ∈ P(n) holds

F_{P} (ρ) ≥ (n − 1) 2\sqrt{3} + (2ρ − \sqrt{3}) p_{0}(n),

with p_{0}(n) = ⌈\sqrt{12n − 3} ⌉ − 3.^{1} Equality holds if and only if P is a so-called extremal Groemerpolygon. That is a Groemerpolygon satisfying E_{Λ}(P) = p_{0} (G_{Λ}(P)) with respect to a critical lattice Λ.

The number p_{0}(n) gives a lower bound for the number of edges of a Groemerpolygon (cf. [11]).^{2} The Theorem holds with equality if and only if the bound is attained, and therefore, an extremal Groemerpolygon exists. The exceptions (n = 121 is the smallest) were studied by Wegner [10] in a second paper. Their exact determination and the determination of packings with minimal convex hull for those n stays still open.

Now, extremal Groemerpolygons are the only polygons with equality in both Theorems. Since F_{P} (ρ) is linear we instantly get

F_{P} (ρ) ≥ (n − 1) 2\sqrt{3} + (2ρ − \sqrt{3}) p_{0}(n),

for n ∈ ℕ, ρ ∈ (\frac{\sqrt{3}}{2}, 1] and P ∈ P(n). Equality holds if and only if P is an extremal

Groemerpolygon. With the same argument we get F_{P} (ρ) ≥ (n − 1)4ρ for ρ ∈ [0, \frac{\sqrt{3}}{2}) with

equality for sausages, the intermediate case ρ = \frac{\sqrt{3}}{2} being covered by Theorem 3.1, with equality for any Groemerpolygon.

In order to see how densest circle packings may look like for parameters bigger than 1, we investigate the problem restricted on lattice packings. First we show for all parameters Theorem 3.3. F_{P} (ρ) becomes minimal for a lattice polygon P and ρ ≥ 0 if and only if P is a critical lattice polygon.

1⌈·⌉ is known as ceiling function (⌈x⌉ being the least integer k with k ≥ x).

2An inductive proof for Wegner’s remark is easy verified using the geometrical definition for p_{0} (Theorem 4.3) and the lemma in Section 6.

Besides Theorems 3.2 and 3.1, many arguments show that Theorem 3.3 holds for arbitrary circle packings and parameters less than \frac{3}{2} + \sqrt{3} = 3.232 . . ..^{3} For lattice packings we have

Theorem 3.4. Theorem 3.2 holds for ρ ∈ (\frac{\sqrt{3}}{2}, \frac{3}{2} + \sqrt{3}) and all lattice polygons P ∈ P(n).

Moreover, the theorem is true for ρ = \frac{3}{2} + \sqrt{3}, if we modify the case of equality to critical lattice polygons with edges having length 2 or 2\sqrt{3} and with the (uniquely defined) smallest circumscribed Groemerpolygon having p_{0}(n) edges.

Six is the smallest number of circles where the second case of equality holds. The corresponding packing, its center-polygon and the smallest circumscribed Groemerpolygon is shown in Figure 2. Unfortunately, it is impossible to give a general lower bound for F_{P} (ρ) with ρ > \frac{3}{2} +\sqrt{3}. Nevertheless, we are able to determine the asymptotic shape (n → ∞) of the best possible polygons. This will be done in a wider context in another paper [8].

Figure 2.

4. Proofs

Proof of Theorem 3.3. The assertion is true for ρ ≤ \frac{\sqrt{3}}{2} (Theorem 3.1) and G_{Λ}(P) ≤ 2. Therefore, we may assume that P has a non-empty interior. This follows from Theorem 3.1 because non-sausage Groemerpolygons define better packings for ρ > \frac{\sqrt{3}}{2}, since their volume is positive.

The remaining proof is constructive: a non-critical lattice Λ will be transformed by regular linear mappings into a critical lattice. The Λ-polygon P becomes a critical lattice polygon P_{0} with the same number of edges and the same number of covered lattice points. The area changes because of Pick’s Identity in dependency of the lattice determinant, which is minimal for the critical lattice (cf. [6]). Hence A(P_{0}) < A(P). We show that the lattice transformation can be chosen that C(P_{0}) < C(P) becomes valid. This proves the Theorem.

To begin with, we choose a reduced basis (cf. [9]) a_{1}, a_{2} for the lattice Λ. A necessary and sufficient condition for being reduced is 0 ≤ 2⟨a_{1}, a_{2}⟩ ≤ ∥a_{1}∥^{2} ≤ ∥a_{2}∥^{2}, if we assume that ∥a_{1}∥ is smaller than ∥a_{2}∥. Now the circumference C(P) can be written as the sum ∑ |AB| over all edges [AB] of P. With fitting numbers m, n ∈ ℤ we have

|AB| = ∥ma_{1} + na_{2}∥ = \sqrt{∥a_{1}∥^{2} m^{2} + 2⟨a_{1}, a_{2}⟩mn + ∥a_{2}∥^{2} n^{2}}.

Now, we first map a_{1} into a′_{1} = \frac{2a_{1}}{∥a_{1}∥} and a_{2} into a′_{2} with ∥a′_{2}∥ = 2 and ⟨a′_{1}, a′_{2}⟩ = \frac{4}{∥a_{1}∥^{2}} ⟨a_{1}, a_{2}⟩. The new basis is reduced because

0 ≤ 2⟨a′_{1}, a′_{2}⟩ = \frac{8}{∥a_{1}∥^{2}} ⟨a_{1}, a_{2}⟩ ≤ 4 = ∥a′_{1}∥^{2} = ∥a′_{2}∥^{2}.

3This would imply a proof for a presumption of Wegner (cf. [10]), which covers the exceptions of Theorem 3.2.

Therefore, the distance from the origin to a lattice point na′_{1} + ma′_{2}, n, m ∈ ℤ\ {0}, is at least as long as the one to a′_{1} and a′_{2}. Hence, the new lattice is a packing lattice for D. An edge [AB] of P is transformed into an edge [A′B′] with

|A′B′| = \sqrt{4m^{2} + 2⟨a′_{1}, a′_{2}⟩mn + 4n^{2}}
≤ \frac{2}{∥a_{1}∥}\sqrt{∥a_{1}∥^{2} m^{2} + 2⟨a_{1}, a_{2}⟩mn + ∥a_{2}∥^{2} n^{2}} ≤ |AB|.

Equality holds if and only if ∥a_{1}∥ = ∥a_{2}∥ = 2. This shows that the new polygon has a smaller circumference if a_{2} is longer than 2.

The next transformation fixes a′_{1} and maps a′_{2} into a′′_{2} with ∥a′′_{2}∥ = 2. The inner product ⟨a′_{1}, a′_{2}⟩ has a fixed value 2x_{0} with x_{0} ∈ [0, 1]. An edge [A′B′] has the length |A′B′| = 2\sqrt{m^{2} + x_{0}mn + n^{2}}. Then the inner product ⟨a′_{1}, a′′_{2}⟩ may be 2x with x ∈ [−1, 1]. Consequently, the packing lattice Λ_{x} with basis a′_{1}, a′′_{2} is critical only for

x ∈ {−1, 1}. Figure 3.

The length of the corresponding edges [A_{x}B_{x}] add up to the circumference c(x) of a Λ_{x}- polygon. The function c(x) is two times differentiable and the length of an edge [A_{x}B_{x}] has a second derivation

\frac{d^{2}}{dx^{2}} |A_{x}B_{x}| = −\frac{m^{2}n^{2}}{2 (n^{2} + xmn + m^{2})^{\frac{3}{2}}} .

Hence, \frac{d^{2}}{dx^{2}} c(x) ≤ 0. Therefore, c(x) attains its minimum either for x = −1 or x = 1, which proves the theorem. □

Proof of Theorem 3.4. The theorem is true for ρ ≤ 1 as a consequence of Theorem 3.2. In order to prove the rest of the assertion it is sufficient to prove it for ρ = \frac{3}{2} + \sqrt{3} = \frac{\sqrt{3}}{4−2\sqrt{3}} because F_{P} (ρ) is a linear function. Because of Theorem 3.3 we may further assume that P is a critical lattice polygon with respect to Λ.

The smallest circumscribed Groemerpolygon P_{G} of P is uniquely defined, since every Groemerpolygon is an intersection of six fixed half-spaces (all bordered by edges of length 2) and vice versa. P_{G} has at least p_{0}(n) edges because p_{0} is monotonically increasing, and because p_{0} gives a lower bound for the number of edges of a Groemerpolygon (cf. [11]).

Now, let e_{p}(l) denote the number of edges with length l of P. With Pick’s identity we get

F_{P} (ρ) = (n − 1)2\sqrt{3} − \sqrt{3} · E_{Λ}(P) + ρ · C(P)
= (n − 1)2\sqrt{3} + ∑_{l} (l · ρ − \sqrt{3}) e_{P} (l),

where the sum is taken over all possible l in Λ. For l ≥ 2\sqrt{3} we get with fitting natural numbers m_{l} ≥ n_{l}

l = 2\sqrt{m_{l}^{2} + m_{l}n_{l} + n_{l}^{2}} = 2\sqrt{\frac{3}{4}(m_{l} + n_{l})^{2} + \frac{1}{4}(m_{l} − n_{l})^{2}} ≥ \sqrt{3} (m_{l} + n_{l})

= (2\sqrt{3} − 2) (m_{l} + n_{l}) + (2 − \sqrt{3}) (m_{l} + n_{l})
≥ (2 − (4 − 2\sqrt{3})) (m_{l} + n_{l}) + (4 − 2\sqrt{3}) .

Equality holds if and only if m_{l} = n_{l} = 1. Hence, F_{P} (ρ) for ρ = \frac{\sqrt{3}}{4−2\sqrt{3}} evaluates to

F_{P} (ρ) = (n − 1)2\sqrt{3} + (2 · ρ − \sqrt{3}) e_{P} (2) + ∑_{l≥2\sqrt{3}} (l · ρ − \sqrt{3}) e_{P} (l)
≥ (n − 1)2\sqrt{3} + (2 · ρ − \sqrt{3}) e_{P} (2) + ∑_{l≥2\sqrt{3}} (2 · ρ − \sqrt{3}) (m_{l} + n_{l}) e_{P} (l)
= (n − 1)2\sqrt{3} + (2 · ρ − \sqrt{3}) ∑_{l}(m_{l} + n_{l}) e_{P} (l).

This proves the theorem because of E_{Λ}(P_{G}) = ∑_{l}(m_{l} + n_{l}) e_{P} (l) ≥ p_{0}(n). □

References

[1] Betke, U.; Henk, M.; Wills, J. M.: Finite and Infinite Packings. J. Reine Angew. Math. 453 (1994), 165–191.

[2] Graham, R. L.; Witsenhausen, H. S.; Zassenhaus, H. J.: On Tightest Packings in the Minkowski Plane. Pacific J. Math. 41 (1972), 699–715.

[3] Gritzmann, P.; Wills, J. M.: Finite Packing and Covering. In: Handbook of Convex Geometry, P. M. Gruber, J. M. Wills (eds.), North Holland, Amsterdam 1993.

[4] Gritzmann, P.; Wills, J. M.: Lattice Points. In: Handbook of Convex Geometry, P. M. Gruber, J. M. Wills (eds.), North Holland, Amsterdam 1993.

[5] Groemer, H.: Über die Einlagerung von Kreisen in einen konvexen Bereich. Math. Z. 73 (1960), 285–294.

[6] Gruber, P. M.; Lekkerkerker, C. G.: Geometry of Numbers. North Holland, Amsterdam 1987.

[7] Oler, N.: An Inequality in the Geometry of Numbers. Acta Math. 105 (1961a), 19–48.

[8] Schürmann, A.: On the Asymptotic Shape of Densest Plane Finite Lattice Packings. In preparation.

[9] Siegel, C. L.: Lectures on the Geometry of Numbers. Springer-Verlag, Berlin-Heidelberg 1989.

[10] Wegner, G.: Extremale Groemerpackungen. Studia Sci. Math. Hung. 19 (1984), 299–302.

[11] Wegner, G.: Über endliche Kreispackungen in der Ebene. Studia Sci. Math. Hung. 21 (1986), 1–28.

Received May 15, 1999