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

Protecting Regular Polygons

Arnfried Kemnitz László Szabó^{1} Zoltán Ujváry-Menyhárt

Diskrete Mathematik, Technische Universität Braunschweig Pockelsstr. 14, D-38106 Braunschweig, Germany

Computer and Automation Institute, Hungarian Academy of Sciences Lágymányosi út 11, H-1111 Budapest, Hungary

Department of Geometry, Eötvös University Rákóczi út 5, H-1088 Budapest, Hungary

Abstract. The minimum number of mutually non-overlapping congruent copies of a convex body K so that they can touch K and prevent any other congruent copy of K from touching K without overlapping each other is called the protecting number of K. In this paper we prove that the protecting number of any regular polygon is three or four, and both values are indeed attained.

1. Introduction

The Newton number N(K) of a convex body K is the maximum number of mutually nonoverlapping congruent copies of K that can touch K. The problem of finding the Newton number of the d-dimensional ball B^{d} is a challenging open problem in discrete geometry for dimensions d ≥ 4, d ≠ 8, 24. Though the answer is trivial for the plane, N(B^{2}) = 6, it is well known that once the exact value of N(B^{3}) was a point of controversy between Sir Isaac Newton and David Gregory. Newton conjectured that the answer is 12 while Gregory thought 13 is also possible. It took almost two hundred years before Hoppe [3] proved that Newton’s conjecture, the ’12’, was correct. But even in the plane the question for N(K) becomes nontrivial if K ≠ B^{2}. The exact value of N(K) is known only for some special convex discs K, e.g., for regular n-gons [1, 5, 7, 8, 10, 11, 12], for Reuleaux triangles [2], for certain isosceles triangles [2, 6, 10], and for certain rectangles [5]. Also, some estimates are given for more general classes of convex discs involving different parameters of the discs, e.g. diameter, width, etc. [2, 4, 9, 10].

1The work was supported by Hungarian State Eötvös Fellowship and by Hungarian Scientific Research Fund No. F019449.

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

In this paper we consider the counterpart of the Newton number problem, i.e., the problem of finding the minimum number of mutually non-overlapping congruent copies of a convex body K so that they can touch K and prevent any other congruent copy of K from touching K without overlapping each other. This quantity will be called the protecting number of K.

We note the existence of a more restrictive variant of the above problem, the so called blocking number problem introduced in [13]. The blocking number of a convex body K is the minimum number of mutually non-overlapping translates of K so that they can touch K and prevent any other translates of K from touching K without overlapping each other. It is proved in [13] that the blocking number of any plane convex body is four.

Turning back to the protecting number it is clear that the protecting number of B^{2} is four. However, the protecting number problem is less trivial for convex bodies different from B^{2}. It is easy to see that the protecting number of any plane convex body K is at least three. Indeed, if K_{1} and K_{2} are two non-overlapping copies of K which touch K then the convex cone or strip containing K and surrounded by the lines separating K from K_{1} and K_{2}, respectively, can always contain a third copy of K which touches K. In this paper we concentrate on regular polygons and first we prove

Theorem 1. The protecting number of any regular polygon is not greater than four.

This theorem together with the above observation shows that the protecting number of any regular polygon is three or four. We also prove that these values are indeed attained and, in addition, the value three is attained infinitely many times.

Theorem 2. The protecting number of the square is four.

Theorem 3. The protecting number of the regular 6n-gon is three for all positive integers n.

Finally, we mention a rather surprising consequence of the last theorem. There exists a convergent sequence of convex discs (with respect to the usual Hausdorff metric) with protecting numbers three such that the protecting number of the limit disc is four. We note, however, that there do not exist convergent sequences of convex discs with protecting numbers four such that the protecting number of the limit disc is three. The proof of this latter statement is easy and is left to the reader.

2. Proof of Theorem 1

First, let K be a regular n-gon, where n ≥ 8 and n ≠ 9, 13, and let K_{1}, K_{2}, K_{3}, K_{4} be the images of K under the reflections with respect to the sides of K with indices ⌊\frac{n}{4}⌋, ⌊\frac{n}{2}⌋, ⌊\frac{3n}{4}⌋, n, respectively. Then K_{1}, K_{2}, K_{3}, K_{4} are mutually non-overlapping. Consider a further congruent copy K′ of K which does not overlap K, K_{1}, K_{2}, K_{3}, K_{4}. Then the incircle of K′ also does not overlap K, K_{1}, K_{2}, K_{3}, K_{4}, of course. The angle between any two consecutive pairs of the halflines emanating at the center of K and going through the centers of K_{1}, K_{2}, K_{3}, K_{4} is at most ⌈\frac{n}{4}⌉\frac{2π}{n} which is not greater than \frac{3π}{5}. Easy calculation shows that the distance between the centers of K and K′ is greater than the diameter of the circumcircle of K which implies that K and K′ are disjoint. Thus K_{1}, K_{2}, K_{3}, K_{4} form a protecting system for K.

In Section 4 we will prove that the protecting number of the regular hexagon is three so it remains to show that the protecting number is not greater than four for n = 3, 4, 5, 7, 9, 13. Figure 2.1 shows protecting systems consisting of four elements in these cases. The proof of the fact that these systems are indeed protecting systems is similar to the previous argument and is left to the reader.

Figure 2.1 Protecting systems for regular 3-, 4-, 5-, 7-, 9-, 13-gons 3. Proof of Theorem 2

According to Theorem 1 it is enough to show that three unit squares cannot protect a unit square. Let S be the unit square with vertices A(0, 0), B(1, 0), C(1, 1), D(0, 1) and suppose, for contradiction, that a collection S = {S_{1}, S_{2}, S_{3}} of three unit squares is a protecting system for S. Consider the four images of S under the reflections with respect to the points A, B, C, D. Each of these four squares is overlapped by the union of S since S is a protecting system for S. Furthermore there are two squares among the above four squares which are overlapped by the same member of S. Without loss of generality we may assume that S_{1} overlaps the images of S under the reflections with respect to the points C and D. Let E, F, G, H denote the vertices of S_{1} in the counterclockwise order such that E lies in the relative interior of the side \overline{CD}.

PSfrag replacements

A
B
C
D
E
F
G
H
x
α
β
γ

Figure 3.1

We claim that ∡HDC +∡DCF < \frac{5π}{4}. For convenience, introduce the angles α = ∡HDC − \frac{π}{2}, β = ∡DCF − \frac{π}{2}, γ = ∡F EC and let x denote the length of the segment \overline{DE} (see Figure 3.1). Then

tan α = \frac{sin γ − x}{cos γ} and tan β = \frac{cos γ + x − 1}{sin γ}

and thus

tan(α + β) = \frac{tan α + tan β}{1 − tan α tan β}

= \frac{sin γ(sin γ − x) + cos γ(cos γ + x − 1)}{sin γ cos γ − (sin γ − x)(cos γ + x − 1)}

= \frac{1 + x(cos γ − sin γ) − cos γ}{x^{2} − x + x(cos γ − sin γ) + sin γ} .

It is enough to show that tan(α + β) < 1, i.e.,

1 + x(cos γ − sin γ) − cos γ < x^{2} − x + x(cos γ − sin γ) + sin γ

or, equivalently,

x(1 − x) < sin γ + cos γ − 1.  (1)

If we translate S_{1} parallel to CD towards the midpoint of \overline{CD} then the right hand side of inequality (1) does not change while the left hand side increases. If α or β becomes zero during this translation then we stop in that position. Otherwise we translate S_{1} until E reaches the midpoint of \overline{CD} and then we rotate S_{1} around E clockwise if γ ≤ \frac{π}{4} and counterclockwise if γ > \frac{π}{4} until α or β becomes zero. During this rotation the right hand side of inequality (1) decreases while the left hand side does not change. Thus it is enough to prove inequality (1) when α or β is zero. By symmetry, we may assume that α = 0. Then inequality (1) is equivalent with the inequality

sin γ(1 − sin γ) < sin γ + cos γ − 1,

i.e., cos^{2} γ < cos γ which holds for 0 < γ < \frac{π}{2} trivially. This proves the claim.

Next consider the square S′ with vertices (0, 1), (− sin α, 1+cos α), (− sin α−cos α, 1+cos α− sin α), (− cos α, 1 − sin α). Since S_{1} does not overlap this square, S_{2} or S_{3}, say S_{2}, overlaps it. Let J be that point of \overline{AB} whose distance from A is sin α(sin α + cos α). We show that the half line emanating at J and having direction vector (−1, −1) does not intersect S_{2}. This trivially holds if S_{2} has points on \overline{CD} thus we have to deal with two cases only,

(1) a vertex of S_{2} lies in the relative interior of \overline{AD},

(2) A lies on the boundary of S_{2}.

Let K, L, M, N denote the vertices of S_{2} in the counterclockwise order.

Case 1. Without loss of generality we may assume that K lies on \overline{AD}. For convenience, introduce the angle φ = ∡AKN. If φ > \frac{π}{4} then we are done. On the other hand, if φ ≤ \frac{π}{4} then L = (− cos φ, 1 − x) for some x < sin α since S_{2} overlaps S′, and thus N = (− sin φ, 1 − x − cos φ − sin φ). The line going through N and having direction vector (1, 1) is a support line of S_{2}. The intersection point of this line with the line AB has coordinates (0, x − 1 + cos φ) and this point is on the left of J since

x − 1 + cos φ < sin α − 1 + cos φ ≤ sin α ≤ sin α(sin α + cos α).

Case 2. Without loss of generality we may assume that A lies on \overline{KL}. For convenience, introduce the angle φ = ∡DAL. We will distinguish three cases, (2.1) φ ≤ α, (2.2) α < φ ≤ \frac{π}{4}, (2.3) \frac{π}{4} < φ.

Case 2.1. The line going through K and having direction vector (1, 1) is a support line of S_{2}. The intersection point of this line with the line AB has coordinates (\overline{AK}(sin φ+cos φ), 0) and this point is on the left of J since sin φ + cos φ ≤ sin α + cos α and \overline{AK} < sin α. The first estimate follows from the fact that the function sin φ + cos φ is monotone increasing on the interval 0 ≤ φ ≤ \frac{π}{4} while the second estimate follows from the fact that the vertex L must lie above the lowest vertex of S′.

Case 2.2. The line going through K and having direction vector (1, 1) is a support line of S_{2}. The intersection point of this line with the line AB has coordinates (\overline{AK}(sin φ + cos φ), 0).

Now \overline{AL} is greater than the distance of A from S′ which is cos α and thus \overline{AK} < 1 − cos α. On the other hand sin φ + cos φ ≤ \sqrt{2} holds trivially. To prove that the above intersection point is on the left of J it is enough to show that

\sqrt{2}(1 − cos α) < sin α(sin α + cos α)

or, equivalently,

\sqrt{2} < sin^{2} α + sin α cos α + \sqrt{2} cos α  (2)

for 0 < α < \frac{π}{4}. The derivative of the right hand side of (2) is

sin 2α + cos 2α − \sqrt{2} sin α = \sqrt{2} sin (2α + \frac{π}{4} ) − \sqrt{2} sin α > 0

for 0 < α < \frac{π}{4} hence the right hand side of (2) is a monotone increasing function on the interval 0 ≤ α ≤ \frac{π}{4}. Taking the fact that the right hand side of (2) is \sqrt{2} for α = 0 into account the assertation follows.

Case 2.3. The line going through N and having direction vector (1, 1) is a support line of S_{2}. The distance of N from S′ is greater than one since the second coordinate of the lowest vertex of S′ is 1−sin α > 1− \frac{\sqrt{2}}{2} while the second coordinate of N is less than − sin φ ≤ −\frac{\sqrt{2}}{2}. Rotate S_{2} around N counterclockwise until S_{2} and S′ touch each other. During this rotation S_{2} cannot overlap S. Observe that after the rotation L cannot be on the boundary of S′ otherwise ∡DLN would be smaller than \frac{π}{2}. However, ∡DLN ≥ ∡DLA + ∡KLN > \frac{π}{2} since ∡LDA < \frac{π}{2} and \overline{LD} ≤ \overline{DA} in the triangle ADL. Therefore after the rotation the lowest vertex of S′ lies on \overline{LK} and the line LK does not intersect the interior of S. Now translate S_{2} along the line LK until L coincides with the lowest vertex of S′ and then rotate S_{2} around L counterclockwise until S_{2} touches S (see Figure 3.2).

PSfrag replacements

A
B
C
D
K
L
M
N
S
S_{2}
α
φ
S′

Figure 3.2

Note that during the above three transformations the line going through N and having direction vector (1, 1) remains a support line of S_{2} and the first coordinate of the intersection point of this line with the line AB does not decrease. Moreover, after the transformations this intersection point has coordinates (\sqrt{2}(sin \frac{α}{2} + cos \frac{α}{2}) − 1 + sin α − cos α, 0). To prove that this intersection point is on the left of J it is enough to show that

\sqrt{2} (sin \frac{α}{2} + cos \frac{α}{2}) − 1 + sin α − cos α < sin α(sin α + cos α)

or, equivalently,

\sqrt{2} (sin \frac{α}{2} + cos \frac{α}{2}) + (1 − cos α)(sin α − cos α) < 2

for 0 < α < \frac{π}{4}. But this inequality holds trivially since sin \frac{α}{2}+cos \frac{α}{2} < \sqrt{2} and sin α−cos α ≤ 0 for 0 < α < \frac{π}{4}.

Thus the halfline emanating at that point of \overline{AB} whose distance from A is sin α(sin α + cos α) and having direction vector (−1, −1) does not intersect S_{2}. Repeating the above argument with the square with vertices (1, 1), (1 + cos β, 1 − sin β), (1 + sin β + cos β, 1 + cos β − sin β), (1 + sin β, 1 + cos β) we conclude that the halfline emanating at that point of \overline{AB} whose distance from B is sin β(sin β + cos β) and having direction vector (1, −1) does not intersect S_{3}.

To complete the proof, i.e. to prove that S cannot be a protecting system for S, it is enough to show that

sin α(sin α + cos α) + sin β(sin β + cos β) ≤ 1

if α + β ≤ \frac{π}{4}. Indeed, in this case the square whose diameters are parallel to the coordinate axes and whose topmost vertex is J does not overlap the elements of S. Since the function cos β + sin β is monotone increasing on the interval 0 ≤ β ≤ \frac{π}{4}

sin β(sin β + cos β) ≤ sin (\frac{π}{4} − α) (sin (\frac{π}{4} − α) + cos (\frac{π}{4} − α))

= cos α(cos α − sin α)

from which the assertation follows. This finishes the proof of Theorem 2.

4. Proof of Theorem 3

We have already seen that the protecting number is at least three thus it is enough to show that three non-overlapping congruent copies K_{1}, K_{2}, K_{3} of a regular 6n-gon K can protect K. Let A_{1}, A_{2}, A_{3} be the midpoints of the sides of K with indices 2n, 4n, 6n, respectively, where the sides are counted counterclockwise. Set K_{i} such that the center O_{i} of K_{i} is collinear with A_{i} and the center O of K, and A_{i} is a vertex of K_{i}, i = 1, 2, 3. Let K′ be a further congruent copy of K which does not overlap K, K_{1}, K_{2}, K_{3}. Without loss of generality we may assume that the center O′ of K′ lies in the convex region bounded by the halflines emanating at O and going through O_{1} and O_{2}, respectively. Let B_{1} be the image of A_{1} under the rotation around O_{1} clockwise by an angle \frac{π}{3}. Similarly, let B_{2} be the image of A_{2} under the rotation around O_{2} counterclockwise by an angle \frac{π}{3}. Then B_{1} and B_{2} are vertices of K_{1} and K_{2}, respectively. Let r and R denote the radii of the incirle and the circumcircle of K, respectively. The incircle of K′ does not overlap K_{1} and K_{2} hence the distance of O′ from the triangles A_{1}B_{1}O_{1} and A_{2}B_{2}O_{2} is at least r. Therefore the distance of O′ from K is at least R with equality if and only if O′ coincides with the intersection point of the lines O_{1}B_{1} and O_{2}B_{2}. In the case of equality B_{1} and B_{2} are midpoints of sides of K′ which implies that \overline{OO′} goes through the midpoint of a side of K′. Thus K′ is disjoint from K, i.e., K_{1}, K_{2}, K_{3} protect K.

5. Concluding remarks

In this paper we have proved that the protecting number of any regular polygon is three or four, and both of these values are indeed attained. We conjecture that this statement remains true for the class of all plane convex bodies as well.

Conjecture 1. The protecting number of any plane convex body is three or four.

Finally we note that the protecting number problem seems to be interesting for not necessarily convex discs as well (a disc is a subset of the plane homeomorphic to B^{2}). It is easy to see that the protecting number of any disc is at least two. On the other hand, certain discs can be protected by two non-overlapping congruent copies of themselves (see Figure 5.1).

Figure 5.1 Non-convex disc with protecting number two

References

[1] Böröczky, K.: Über die Newtonsche Zahl regulärer Vielecke. Period. Math. Hungar. 1 (1971), 113–119.

[2] Fejes Tóth, L.: On the number of equal discs that can touch another of the same kind. Studia Sci. Math. Hungar. 2 (1967), 363–367.

[3] Hoppe, R.: Bemerkungen der Redaktion zu ’Bender, C., Bestimmung der größten Anzahl gleich grosser Kugeln, welche sich auf eine Kugel von demselben Radius wie die übrigen auflegen lassen. Arch. Math. Phys. 56 (1874), 302–306.’ Ibid. 307–312.

[4] Hortobágyi, I.: Über die auf Scheibenklassen bezügliche Newtonsche Zahl der konvexen Scheiben. Ann. Univ. Sci. Budapest. Rolando Eötvös Nom. Sect. Math. 18 (1975), 123– [5] Kemnitz, A.; Möller, M.: On the Newton number of rectangles. In: Intuitive Geometry,

(Budapest 1995), Bolyai Society Mathematical Studies 6, eds. Bárány, I.; Böröczky, K.: János Bolyai Mathematical Society, Budapest 1997, 373–381.

[6] Kemnitz, A.; Wojzischke, D.: On the Newton number of isosceles triangles. Periodica Math. Hungar. (to appear).

[7] Klamkin, M. S.; Lewis, T.; Liu, A.: The kissing number of the square. Math. Mag. 68 (1995), 128–133.

[8] Linhart, J.: Die Newtonsche Zahl von regelmäßigen Fünfecken. Period. Math. Hungar. 4 (1973), 315–328.

[9] Schopp, J.: Über die Newtonsche Zahl einer Scheibe konstanter Breite. Studia Sci. Math. Hungar. 5 (1970), 475–478.

[10] Wegner, G.: Relative Newton numbers. Monatsh. Math. 114 (1992), 149–160.

[11] Youngs, J. W. T.: A lemma on squares. Amer. Math. Monthly 46 (1939), 20–22.

[12] Zhao, L.: The kissing number of the regular polygon. Discrete Math. 188 (1998), 293– 296.

[13] Zong, C.: Packing and covering. Ph. D. Thesis, TU Wien, 1993.

Received December 16, 1998; revised version April 30, 1999