Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 40 (1999), No. 1, 217-227.

What is the Minimum Length of a Non-Extendable Lace?

Arnfried Kemnitz Valeriu Soltan^{∗}

Abt. Diskrete Mathematik, Techn. Universität Braunschweig D-38106 Braunschweig, Germany

Mathematical Institute, Academy of Sciences of Moldova MD–2028 Chişinău, Moldova

Abstract. A family {C_{1}, …, C_{n}} of pairwise distinct, non-overlapping, congruent circles in the plane form a lace provided C_{i} touches C_{i+1} for all i = 1, …, n − 1. If, additionally, C_{n} touches C_{1}, the lace is named a loop. A lace (loop) {C_{1}, …, C_{n}} is called extendable if it is properly contained in another lace (respectively, loop). In the paper various problems and results on minimum lengths of non-extendable laces and loops are discussed. MSC 1991: 52C15 Keywords: finite packing, circles, plane

1. Main Problems and Results

According to [1], a family of n non-overlapping congruent circles C_{1}, …, C_{n} form a snake of length n provided C_{i} touches C_{j} if and only if |i − j| = 1. We will say that a snake {C_{1}, …, C_{n}} is extendable provided it is a proper subset of another snake. (Note that in [1] and [2] non-extendable snakes are called limited and maximal, respectively.)

It is proved in [1] that the minimum length of a non-extendable snake formed by congruent circles is 10. This assertion is generalized in [2] for the case of an arbitrary planar convex body. Namely, it is proved that the minimum length of a non-extendable snake formed by translates of a given planar convex body K is 11 if K is a parallelogram and is 10 otherwise.

∗Supported by Technical University of Braunschweig.

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

For the sake of completeness, we mention here one more related result: it was proved in [4], confirming a conjecture from [3], that the minimum length of a non-extendable snake formed by edge-to-edge touching squares is 19.

Here we modify the definition of snake as follows. We say that a family {C_{1}, …, C_{n}} of pairwise distinct, non-overlapping, congruent circles form a lace of length n if C_{i} touches C_{i+1} for all i = 1, …, n − 1. If, additionally, C_{n} touches C_{1}, the lace is called a loop of length n. Following the graph-theoretic terminology, C_{1}, …, C_{n} form a lace (loop) if and only if there is a Hamiltonian path (respectively, a Hamiltonian cycle) through the skeleton of the family.

Further, a lace (loop) {C_{1}, …, C_{n}} is called extendable provided it is a proper subfamily of another lace (respectively, loop). A lace (loop) of length n is weakly extendable if it is a subfamily of a lace (respectively, loop) of length n + 1. It is easily seen that any loop is extendable to a lace.

Figure 1: A weakly non-extendable lace of length 20 formed by congruent circles.

Figure 2: A weakly non-extendable loop of length 14 formed by congruent circles.

Conjecture 1. The minimum length of a weakly non-extendable lace formed by congruent circles is 20.

Theorem 1. The minimum length of a weakly non-extendable loop formed by congruent circles is 14.

Conjecture 2. The minimum length of a non-extendable lace or loop formed by congruent circles is 21.

Figure 3: A non-extendable loop of length 21 formed by congruent circles.

Remark. An example of a non-extendable lace of length 21 formed by congruent circles can be obtained from the loop in Figure 3 by making two central circles disjoint.

The following two assertions give initial steps towards proofs of Conjectures 1 and 2.

Theorem 2. The length of a weakly non-extendable lace formed by congruent circles is at least 15.

Theorem 3. The length of a non-extendable loop formed by congruent circles is at least 15. The above considerations can be obviously generalized for the case of laces or loops formed by translates of a given planar convex body. The following result shows that in this case even the existence of a finite weakly non-extendable lace or loop is not guaranteed.

Theorem 4. Any finite lace or loop formed by translates of a given square is weakly extendable.

Clearly, Theorem 4, as well as its proof, also hold for the case of a parallelogram.

We enclose this section with some open problems.

Problem 1. Do there exist finite non-extendable, even weakly non-extendable, laces or loops formed by translates of any given planar convex body distinct from the parallelogram and circles?

Problem 2. What is the minimum length of a non-extendable snake formed by congruent copies of a given planar convex body?

Problem 3. What is the minimum length of a non-extendable (weakly non-extendable) lace or loop formed by congruent copies of a given planar convex body?

2. Proofs

Proof of Theorem 1

Since Figure 2 gives an example of a weakly non-extendable loop of length 14 formed by congruent circles, it remains to show that the length of any weakly non-extendable loop of congruent circles is at least 14.

Let L = {C_{1}, …, C_{n}} be a weakly non-extendable loop formed by congruent circles of radii 1, say, and let b_{i} be the center of C_{i}, i = 1, …, n. Clearly, b_{1}, …, b_{n} are the vertices of a simple closed polygonal line, L, formed by n closed line segments [b_{i}, b_{i+1}], i = 1, …, n, of length two each (here we put b_{n+1} = b_{1}). Denote by P the convex hull of L, and let b_{i_{1}}, …, b_{i_{m}}, 1 ≤ i_{1} < ⋯ < i_{m} ≤ n, be the vertices of P. Since b_{1}, …, b_{n} are not on a line, P has nonempty interior and therefore m ≥ 3.

Lemma 1. One has 1 < i_{l} − i_{k} < n − 1 for any 1 ≤ k < l ≤ m. In particular, n ≥ 2m.

Proof. Assume for a moment that i_{l} − i_{k} = 1 for a pair of integers 1 ≤ k < l ≤ m (the case i_{l} − i_{k} = n − 1 is similar). This means that l = k + 1 and hence the segment [b_{i_{k}}, b_{i_{k+1}}] is a side of P. Since P is convex, it lies entirely in a closed half-plane, H, determined by the line through b_{i_{k}} and b_{i_{k+1}}. If C is the circle of radius 1 touching both C_{i_{k}}, C_{i_{k+1}} and lying outside H, then {C_{1}, …, C_{i_{k}}, C, C_{i_{k+1}}, …, C_{n}} is a loop properly containing L, a contradiction. □

Lemma 2. Every interior angle of P is of more than 120^{∘}.

Proof. Let b_{r} be a vertex of P. After a certain renumbering (if necessary) we may assume that 1 < r < m. In this case the angle ^{}b̸_{r−1}b_{r}b_{r+1} is less than 180^{∘}. Due to Lemma 1, neither b_{r−1} nor b_{r+1} is a vertex of P. Since both circles C_{r−1} and C_{r+1} touch C_{r} and do not overlap each other, one has ^{}b̸_{r−1}b_{r}b_{r+1} ≥ 60^{∘}. Denote by C′ the circle of radius 1 which touches both C_{r} and C_{r−1} and whose center lies outside the convex angular region R formed by the half-lines [b_{r}, b_{r−1}) and [b_{r}, b_{r+1}), as shown in Figure 4. By the hypothesis, {C_{1}, …, C_{r−1}, C′, C_{r}, …, C_{n}} is not a loop. Hence C′ overlaps a circle C_{k} ∈ L. It is easily seen that the last is possible only if b_{k} lies outside the region R and ^{}b̸_{k}b_{r}b_{r−1} > 30^{∘}. By a similar argument, there is a circle C_{j} ∈ L, such that its center b_{j} lies outside R and b̸_{r+1}b_{r}b_{j} > 30^{∘}.

Summing up, we have that the interior angle of P with the apex b_{r} is at least

b̸_{k}b_{r}b_{j} = ^{}b̸_{k}b_{r}b_{r−1} +^{}b̸_{r−1}b_{r}b_{r+1} +^{}b̸_{r+1}b_{r}b_{j} > 120^{∘}.  □

C′  R  b_{j} b_{r} b_{k}  b_{r+1} b_{r−1}

Figure 4: A step in the proof of Lemma 2.

Now we are able to show that n ≥ 14. Indeed, the sum of all interior angles of P equals 180^{∘}(m − 2), where m is the number of vertices of P. According to Lemma 2, we have 180^{∘}(m − 2) > 120^{∘}m, i.e., m > 6. From Lemma 1 it follows that n ≥ 2m ≥ 14. □

Proof of Theorem 2

Proof of Theorem 2 is similar to that of Theorem 1. Let L = {C_{1}, …, C_{n}} be a weakly non-extendable lace formed by congruent circles of radii 1, say, and let b_{i} be the center of C_{i}, i = 1, …, n. The points b_{1}, …, b_{n} are the vertices of a simple self-nonintersecting polygonal line, L, formed by n line segments [b_{1}, b_{2}], …, [b_{n−1}, b_{n}] such that ∥b_{i} − b_{i+1}∥ = 2 for all i = 1, …, n − 1 and ∥b_{1} − b_{n}∥ > 2. Denote by P the convex hull of L, and let b_{i_{1}}, …, b_{i_{m}}, 1 ≤ i_{1} < ⋯ < i_{m} ≤ n, be the vertices of P. Since b_{1}, …, b_{n} are not on a line, P has nonempty interior and whence m ≥ 3.

Lemma 3. One has 1 < i_{1} and i_{m} < n.

Proof. Assume, for contradiction, that i_{1} = 1 (the case i_{m} = n is similar). This means that b_{1} is a vertex of P, and one can easily draw a circle C′ touching C_{1} such that C′ is outside P and its center lies on the bisector line of the angle ^{}b̸_{i_{m}}b_{1}b_{i_{2}}. Clearly, C′ touches only one of the circles C_{i} ∈ L, namely C_{1}. This implies that {C′, C_{1}, …, C_{n}} is a lace properly containing L, a contradiction. □

By repeating the proof of Lemma 1, which holds also for the case when L is a lace, we obtain that 1 < i_{l} − i_{k} for any integers 1 ≤ k < l ≤ m. This and Lemma 3 imply the inequality n ≥ 2m + 1.

Since Lemma 2 also holds for the case of laces, we get that every interior angle of P is of more than 120^{∘}. As in Theorem 1, the last implies m ≥ 7, and hence n ≥ 2m + 1 ≥ 15. □

Proof of Theorem 3

Let L = {C_{1}, …, C_{14}} be a loop of length 14 formed by congruent circles of radii 1, say. If L is weakly extendable, it is also extendable. Hence it remains to consider the case when L is weakly non-extendable.

Denote by b_{i} the center of C_{i}, i = 1, …, 14. As it is shown in the proof of Theorem 1, the convex hull of {b_{1}, …, b_{14}} is a convex polygon, P, with at least seven vertices such that no two points of the form b_{i}, b_{i+1}, i = 1, …, 14, are simultaneously vertices of P (here we put b_{15} = b_{1}). Hence P is a convex heptagon with the vertices b_{1}, b_{3}, b_{5}, b_{7}, b_{9}, b_{11}, b_{13}, say.

Let Q be the simple polygon with the vertices b_{2}, b_{4}, b_{6}, b_{8}, b_{10}, b_{12}, b_{14} (see Figure 5).

Lemma 4. The polygon Q is a convex heptagon.

Proof. To prove this, consider the isosceles triangles Δ(b_{1}b_{2}b_{3}) and Δ(b_{2}b_{3}b_{4}), where

∥b_{1} − b_{2}∥ = ∥b_{2} − b_{3}∥ = ∥b_{3} − b_{4}∥ = 2.

As it was shown in the proof of Lemma 2, ^{}b̸_{1}b_{3}b_{2} > 30^{∘} and ^{}b̸_{2}b_{3}b_{4} ≥ 60^{∘}. Hence ^{}b̸_{1}b_{2}b_{3} < 120^{∘} and ^{}b̸_{3}b_{2}b_{4} ≤ 60^{∘}. Similarly, ^{}b̸_{1}b_{2}b_{14} ≤ 60^{∘}.

b_{1}  b_{2}  b_{3}  b_{5} b_{12} b_{14}  b_{4} b_{13} b_{11}  b_{6} b_{7} b^{9} b_{8} b_{10}
Figure 5: Polygon Q with vertices b_{2}, b_{4}, b_{6}, b_{8}, b_{10}, b_{12}, b_{14}.

As a result, the interior angle ^{}b̸_{4}b_{2}b_{14} of the polygon Q is more than 120^{∘}. By the same argument, any interior angle of Q is more than 120^{∘}.

The sum of interior angles of the heptagon Q equals 900^{∘}, while the sum of any six of them is more than 720^{∘}. Hence each of the interior angles of Q is less than 180^{∘}, i.e., Q is a convex heptagon. □

Lemma 5. There is a circle of radius 1, lying inside the heptagon Q such that it touches C_{2} and is disjoint to any of the circles C_{i}, i = 4, 6, 8, 10, 12, 14.

Proof. Denote by C the circle of radius 1 lying inside the polygon Q and touching the circle C_{2} such that the center of C lies on the bisector line of the interior angle ^{}b̸_{4}b_{2}b_{14} of Q (see Figure 6).

We claim that C does not intersect any of the circles C_{4}, C_{6}, C_{8}, C_{10}, C_{12}, C_{14}. Due to the symmetry argument it is sufficient to show that C does not intersect any of C_{4}, C_{6}, C_{8}.

Denote by b the center of C and consider the triangle Δ(b, b_{2}, b_{4}). Since 120^{∘} < ^{}b̸_{4}b_{2}b_{14} < 180^{∘} (see Lemmas 2 and 4) and since b lies on the bisector line of the angle ^{}b̸_{4}b_{2}b_{14}, one has 60^{∘} < ^{}b̸b_{2}b_{4} < 90^{∘}. Having in mind that ∥b_{2} − b_{4}∥ ≥ ∥b − b_{2}∥ = 2, we get ∥b − b_{4}∥ > 2. This implies that C is disjoint to C_{4}.

C  b_{4} b_{6} b_{12}  b′_{2} b_{14}  b_{2} b^{10}  b_{8}  b′_{8} b

Figure 6: Unit circle C inside polygon Q.

Clearly, [b, b_{2}] is the shortest side of the triangle Δ(bb_{2}b_{4}). Then ^{}b̸_{2}b_{4}b < 60^{∘}, and hence

b̸b_{4}b_{6} = ^{}b̸_{2}b_{4}b_{6} −^{}b̸_{2}b_{4}b > 120^{∘} − 60^{∘} = 60^{∘}.

Considering the triangle Δ(bb_{4}b_{6}), we have, as above, ∥b − b_{6}∥ > 2, i.e., C is disjoint to C_{6}. It remains to show that C is disjoint to C_{8}. Since

∥b − b_{8}∥ ≥ ∥b_{2} − b_{8}∥ − ∥b − b_{2}∥ = ∥b_{2} − b_{8}∥ − 2,

it is sufficient to prove that ∥b_{2} − b_{8}∥ > 4. Indeed, let b′_{2} and b′_{8} be the projections of the points b_{2} and b_{8}, respectively, on the line l through the points b_{4} and b_{6} (see Figure 6). Since b̸_{2}b_{4}b′_{2} = 180^{∘} −^{}b̸_{2}b_{4}b_{6} < 60^{∘}, one has ∥b′_{2} − b_{4}∥ > \frac{1}{2}∥b_{2} − b_{4}∥ ≥ 1. Similarly, ∥b_{6} − b′_{8}∥ > 1, and whence

∥b_{2} − b_{8}∥ ≥ ∥b′_{2} − b′_{8}∥ = ∥b′_{2} − b_{4}∥ + ∥b_{4} − b_{6}∥ + ∥b_{6} − b′_{8}∥ > 4.  □

Lemma 6. There is a circle of radius 1, lying inside the heptagon Q such that it touches both C_{2} and C_{4} and is disjoint to any of the circles C_{i}, i = 6, 8, 10, 12, 14.

Proof. Let C be a circle of radius 1 satisfying the condition of Lemma 5. We rotate continuously C around C_{2} in the direction of C_{4} until it will touch a circle C_{j}, j ∈ {4, 6, 8, 10, 12, 14}. Denote by C′ this new position of C and let b′ be the center of C′.

We are going to prove that j = 4. Due to the orientation of the rotation of C′ around C_{2}, we have 12 ≠ j ≠ 14. Since the inequality ∥b − b_{8}∥ > 2 follows only from the relations ∥b_{2}−b_{8}∥ > 4 and ∥b−b_{2}∥ = 2 (see the proof of Lemma 5), we have, as above, that ∥b′−b_{8}∥ > 2. Similarly, ∥b′ − b_{10}∥ > 2. The last means that 10 ≠ j ≠ 12.

It remains to show that j ≠ 6. Assume, for contradiction, that C′ touches C_{6} and consider the triangles Δ(b′b_{2}b_{4}) and Δ(b′b_{4}b_{6}). Since the line segments [b′, b_{2}] and [b′, b_{6}] are

C_{1}  C_{3} C_{2} C_{14} C′  C_{4} C′′

Figure 7: Unit circles C′ and C′′ in the last step of the proof of Theorem 3.

the shortest sides in these triangles, we have ^{}b̸_{2}b_{4}b′ ≤ 60^{∘} and ^{}b̸′b_{4}b_{6} ≤ 60^{∘}. The last is in contradiction with ^{}b̸_{2}b_{4}b_{6} > 120^{∘} (see Lemma 2). Hence j ≠ 6. □

Now we are ready to finish the proof of Theorem 3. Indeed, let C′ be the circle satisfying the condition of Lemma 6, and denote by C′′ the circle lying outside the heptagon P and touching C_{1} such that the center of C′′ lies on the bisector line of the angle ^{}b̸_{2}b_{1}b_{14}. We rotate continuously C′′ around C_{1} until it will touch C_{3}. (The positions of C′ and C′′ are shown by the shaded circles in Figure 7). The circle C′′ is disjoint to C_{2} since the loop L is assumed to be weakly non-extendable. Clearly, {C_{1}, C′′, C_{3}, C_{2}, C′, C_{4}, C_{5}, …, C_{14}} is a loop properly containing L. □

Proof of Theorem 4

We will organize the proof of the theorem for both cases (i.e., for laces and loops) simultaneously. Let K be a given square, whose sides are parallel to the coordinate axes in the plane. Assume, for contradiction, the existence of a finite weakly non-extendable lace or loop L = {K_{1}, …, K_{n}} formed by translates of K. Denote by R be the least (under inclusion) rectangle containing L such that its sides are parallel to those of K. In what follows, a, b, c, d denote the vertices of R in the clockwise order of the boundary of R, where [a, b] is the upper horizontal side of R. Clearly, each side of R is touched from inside by a certain translate K_{i} ∈ L.

Claims 1–4 below deal with some preliminary properties of L.

Claim 1. No two squares K_{i} and K_{i+1} simultaneously touch the same side of R.

Assume that for a certain i = 1, …, n both squares K_{i} and K_{i+1} touch the same side of R. In this case we can extend L to L′ = {K_{1}, …, K_{i}, K′, K_{i+1}, …, K_{n}} by adding a new translate K′ of K placed outside R and touching both K_{i}, K_{i+1}. Clearly, L′ is a lace or a loop if and only if so is L. □

Claim 2. None of the squares K_{i}, i = 1, …, n, contains the vertex b of R.

Indeed, assume for a moment that a square K_{i} contains b. If L is a lace and i equals one of the indices 1, n, then one can place outside R a new translate of K having a common side with K_{i}. In this case we get an extension of the lace L.

Let L be a loop. Then K_{i} has in L two neighbours, K_{i−1} and K_{i+1} (we can renumber, if necessary, the members of L to have 1 < i < n). It is easily seen that at least one of the squares K_{i−1}, K_{i+1} has a common side with K_{i} and whence touches a side of R. The last is impossible by Claim 1. □

Claim 3. If L is a lace, then none of the squares K_{1}, K_{n} touches a side of R.

Indeed, if one of the squares K_{1}, K_{n} touched a side of R, then as in the proof of Claim 1, one could extend L to a larger lace by adding a new translate of K exterior to R. □

From Claim 3 it follows that if a square K_{i} touches a side of R, then it has in L two neighbours, K_{i−1} and K_{i+1} (if L is a loop and occasionally i = 1 or i = n, we put i − 1 = n or i + 1 = 1, respectively).

Claim 4. If a square K_{i} touches a side of R along its side [e, f] and [e′, f′] is the second side of K_{i} parallel to [e, f], then both squares K_{i−1}, K_{i+1} touch K_{i} along [e′, f′].

Assume for a moment that K_{i+1} touches K_{i} along a side distinct from [e′, f′]. In this case we can extend L to {K_{1}, …, K_{i}, K′, K_{i+1}, …, K_{n}} by adding a new translate K′ of K, such that K′ touches both K_{i}, K_{i+1}, has a common side with K_{i+1}, and partly lies in R. □

The contradiction with the finiteness of L will be obtained by constructing an infinite sequence S_{1}, S_{2}, … of pairwise distinct members in L.

PSfrag replacements

a
b
c
d
K_{i}

N(K_{i})

Figure 8: Square K_{i} with associated rectangle N(K_{i}).

Before doing this, we need one more notion. In what follows, we associated to any square K_{i} ∈ L disjoint to the side [b, c] of R a rectangle N(K_{i}) whose sides are parallel to those of K, and such that:

(i) the left vertical side of N(K_{i}) conicides with the right vertical side of K_{i}, (ii) the right vertical side of N(K_{i}) lies on the side [b, c] of R (see Figure 8).

Let by K_{i_{1}} the square in L that touches the side [a, b] of R and is the closest to the vertex b. Put S_{1} = K_{i_{1}}. By Claim 1, S_{1} does not contain the vertex b. Clearly, no other square K_{i} ∈ L lies in N(S_{1}). Due to Claim 4, neither of K_{i_{1}−1}, K_{i_{1}+1} overlaps N(S_{1}).

Claim 5. There is a square K_{i} ∈ L overlapping N(S_{1}).

Indeed, suppose that none of the squares in L overlaps N(S_{1}) and consider the translate K′ of K, lying in N(S_{1}) and having with S_{1} a common side. Obviously, the addition of K′ gives an extension of L, since from Claim 4 it follows that K′ touches one of K_{i_{1}−1}, K_{i_{1}+1}. The obtained contradiction shows that at least one square K_{i} overlaps N(S_{1}). □

Now we choose in L a square, which overlaps the rectangle N(S_{1}) and is the closest to the side [a, b] of R. If there are more than one such squares, we choose among them the closest to the side [b, c] of R and denote this square by S_{2}. Note that the existence of S_{2} is guaranteed by Claim 5 and finiteness of L.

Claim 6. The square S_{2} is disjoint to the side [b, c] of R.

Assume, for contradiction, that the square S_{2} touches the side [b, c]. If [v, z] is the upper horizontal side of S_{2}, then consider the translate K′ of K having [v, z] as the lower horizontal side. Due to the choice of S_{1} and to Claim 4, K′ does not overlap any square K_{i} ∈ L and touches one of the squares K_{j−1}, K_{j+1}, where j is the ordinal number of S_{2} in L. This means that L can be extended by the addition of K′, a contradiction. □

Assume that we have constructed a sequence of pairwise distinct squares S_{1}, …, S_{m} ∈ L, m ≥ 2, all disjoint to the side [b, c] of R, and such that for any i = 2, …, m,

(i) S_{i} overlaps the rectangle N(S_{i−1}),

(ii) among all squares overlapping N(S_{i−1}), S_{i} is the closest to the side [a, b], and among all such squares it is the closest to the side [b, c] of R.

We are going to show the existence of the next such square, S_{m+1}.

Claim 7. There is a square S_{m+1} overlapping N(S_{m}) and disjoint to the side [b, c] such that among all such squares S_{m+1} is the closest, firstly, to the side [a, b], and secondly, to the side [b, c] of R.

The proof of Claim 7 follows from that of Claims 5 and 6, with the respective modifications. From the choice of S_{m} (= K_{j}) it follows that none of the neighbours K_{j−1}, K_{j+1} of S_{m} overlaps N(S_{m}), since otherwise we can add to L a new translate of K, as it is described in Claim 4. Then the translate K′ of K, lying in N(S_{m}) and having a common vertical side with S_{m}, touches one of the squares K_{j−1}, K_{j+1}. Since L cannot be extended by the addition of K′, the last overlaps a new square K_{i} ∈ L. Hence there is a square K_{i} overlapping N(S_{m}). Among all such squares we choose in L the closest to the side [a, b] of R, and if there are more than one such squares, we choose among them the closest to the side [b, c] of R. Denote this square by S_{m+1}.

In a similar way, by repeating the proof of Claim 6, we obtain that S_{m+1} is disjoint to the side [b, c] of R. □

Summing up, we get that any finite sequence of squares S_{1}, S_{2}, … ∈ L can be extended to a larger one. The last is in contradiction with the finiteness of L. Hence any finite lace or loop formed by translates of a square is weakly extendable. □

References

[1] Bisztriczky, T.; Böröczky Jr., K.; Harborth, H.; Piepmeyer, L.: On the smallest limited snake of unit disks. Geom. Dedicata 40 (1991), 319–324.

[2] Böröczky Jr., K.; Soltan, V.: Smallest maximal snakes of translates of convex domains. Geom. Dedicata 54 (1995), 31–44.

[3] Harborth, H.: Problem 45: Kleinste endliche Schlange. Math. Semesterber. 36 (1989), 269–270.

[4] Hering, F.: Beweis einer Vermutung von Heiko Harborth über Polyominoes aus Quadraten. Math. Semesterber. 38 (1991), 223–237.

Received January 28, 1998; revised version June 14, 1998