On Malfatti’s Marble Problem
Ulaanbaatar Mongolia
uugnaa.ninjbat@gmail.com
Abstract
Consider the problem of finding three non-overlapping circles in a given triangle with the maximum total area. This is Malfatti’s marble problem, and it is known that the greedy arrangement is the solution. In this paper, we provide a simpler proof of this result by synthesizing earlier insights with more recent developments. We also discuss some related geometric extremum problems, and show that the greedy arrangement solves the problem of finding two non-overlapping circles in a tangential polygon with the maximum total radii and/or area. In the light of this discussion, we formulate a natural extension of Melissen’s conjecture.
Keywords
1 Introduction
In mathematics the art of proposing
a question must be
held higher than solving it.Georg Cantor
Let $\triangle ABC$ be a given triangle in a plane, and let $n\in\mathbb{N}$ be a given number. Consider the following problem.
Problem 1.
Find $n$ non-overlapping circles inside of $\triangle ABC$ so that the sum of their areas is maximal.
When $n=3$, following a paper by Malfatti published in 1803, this problem is known as Malfatti’s marble problem; according to [Szabó et al.2007], this is one of the first examples of a packing problem appeared in European mathematics. Initially, G. Malfatti and others assumed that the solution would be three circles that are tangent to each other and each circle is tangent to two sides of $\triangle ABC$; these circles later became known as the Malfatti circles. However, [Lob and Richmond1930] discovered a case in which the Malfatti circles were not the solution to Malfatti’s marble problem, and [Goldberg1967] showed that they are never the optimal solution. Following this, [Zalgaller and Los1994] gave a complete solution to this problem by showing that the greedy arrangement is the optimal solution.
The greedy arrangement of $n$ circles in $\triangle ABC$ is the result of the $n$-step process where at each step one chooses the largest circle which does not overlap the previously selected circles and is contained by $\triangle ABC$. It is evident that, for $n=1$, the greedy arrangement solves Problem 1. It can be shown that the same is true for $n=2$ [see Theorem 1 in [Andreatta et al.2011], and also Sect. 2.3 in [Andreescu et al.2006]]. As mentioned above, [Zalgaller and Los1994] showed that one can extend this line of reasoning to the case of $n=3$. However, their proof is lengthy with the extensive usage of trigonometric methods.11[Andreescu et al.2006] give a simple proof of [Zalgaller and Los1994]’s result for the case of an equilateral $\triangle ABC$.
In Sect. 2, we provide a simpler proof of the [Zalgaller and Los1994] result by synthesizing their insights with these in [Andreatta et al.2011]. The former paper shows that, for $n=3$, there are fourteen possible arrangements to be considered, and it eliminates each non-greedy arrangement as being non-optimal; the latter paper shows that not only there is an elegant and simple proof of the result for $n=2$, but also the same result holds for other regions including concave triangles. We connect the more difficult case of $n=3$ to the simple case of $n=2$, which, in turn, allows us to focus on seven groups of arrangements instead of fourteen cases, where each group is analyzed in a unified fashion. In addition to clarifying the proof, this approach also substantially reduces trigonometric calculations.
In Sect. 3, we discuss some other related geometric extremum problems and suggest a natural extension of Melissen’s conjecture (see Conjecture 3). We also show that the greedy arrangement solves the problem of finding two non-overlapping circles inscribed into a tangential convex polygon with the maximum total radii and/or area (see Theorem 5). This result generalizes some of the earlier results such as Theorem 1 in [Andreatta et al.2011].
2 The Proof
Mathematical works consist of
proofs, just as poems consist of
characters.Vladimir Arnold
2.1 Preliminaries
A region is a closed, bounded subset of a plane with a positive area. In addition to polygons, we are mainly interested in the following regions: a triangle with three concave sides, which we call a concave triangle; a triangle with one concave side, which we call a semi-concave triangle; and a convex quadrilateral except one concave side, which we call a semi-concave quadrilateral (see Fig. 1a–c respectively). In all cases that we consider, the concave side is a circular arc.
Let us say that $n\in\mathbb{N}$ circles in a region form an arrangement if each of them is contained in the region, and they are non-overlapping. When the region is either a convex polygon, or a concave triangle, or a semi-concave triangle, these circles form a greedy arrangement if they are the result of the $n$-step process, where at each step one chooses the largest circle which does not overlap the previously selected circles and is contained by the region. An arrangement of $n$ circles is rigid if it is not possible to continuously deform one of the circles to increase its radius without moving the others and keeping all circles non-overlapping.22A closely related but stronger notion is the Pareto optimality (PO) which is frequently used in the multi-objective optimization and in economics. PO reads as follows: an arrangement of $n$ circles in a region satisfies PO if it is not possible to rearrange them in a way that some circles get larger but none gets smaller. Notice that the greedy arrangement is a rigid arrangement. An arrangement of $n$ circles is optimal if the sum of their areas is maximal.
Following [Zalgaller and Los1994], we call two arrangements of $n$ circles in a triangle combinatorially identical if the sides of the triangle and the circles in one arrangement can be put in a bijection to these in the other arrangement such that the existence or lack of a common point of a pair “a side and a circle” or “two circles” is preserved under this mapping. Similarly, two arrangements of $n$ circles in a semi-concave triangle/quadrilateral are combinatorially identical if the concave side of the triangle/quadrilateral, straight sides of the triangle/quadrilateral and the circles in one arrangement can be put in a bijection to these in the other arrangement such that the existence or lack of a common point of a pair “a side (concave or straight) and a circle” or “two circles” is preserved under this mapping.
Our starting point is the following observation.
Lemma 1.
Let us consider the problem of arranging $n\in\mathbb{N}$ circles in a region. Then
-
A.
every optimal arrangement is a rigid arrangement, and
-
B.
if the region enclosed by one of the circles in an optimal arrangement is removed, the remaining circles constitute an optimal arrangement in the remaining region.
Proof.
We prove only the first statement; a similar argument applies to the second. Suppose, by contradiction, that an optimal arrangement was not rigid. Then, by definition, it is possible to rearrange the circles in such a way that at least one of them gets larger while none gets smaller. In that arrangement, the total area is larger, which contradicts the optimality of the initial arrangement. $\square$
The following useful result is obtained in the proof of Theorem 2 in [Andreatta et al.2011].
Lemma 2.
Let $AA^{\prime}$ and $CC^{\prime}$ be two non-intersecting segments in $\triangle ABC$. Assume two externally tangent circles are given so that one of the following conditions holds:
-
•
Both circles touch the side $AC$; the first circle touches the interior of $AA^{\prime}$, and the second circle touches the interior of $CC^{\prime}$ (see Fig. 2a).
-
•
The first circle touches the side $AB$ and the interior of $AA^{\prime}$, and the second circle touches the side $BC$ and the interior of $CC^{\prime}$ (see Fig. 2b).
Then the radius $r$ of one of the circles uniquely determines that of the other, $R(r)$, and, moreover, the function describing the sum of their areas is strictly convex with respect to $r$.
For a proof, see [Andreatta et al.2011]; note also that it can be reconstructed easily from the proof of Lemma 3 below. Lemma 2 leads to the following result.
Theorem 1.
Let $n\leq 2$. Then the greedy arrangement is optimal if the region is either a triangle, or a concave triangle, or a semi-concave triangle.
Proof.
The result is obvious for $n=1$; so we assume $n=2$. The optimality of the greedy arrangement if the region is a triangle or a concave triangle is shown in Theorems 1 and 2 in [Andreatta et al.2011]. Thus, we focus on the case of a semi-concave triangle. Let us show that any optimal arrangement must contain the incircle. By Lemma 1A, we need to restrict our attention to rigid arrangements. Notice that there are two combinatorially non-identical rigid arrangements which do not include the incircle, as depicted in Fig. 3, arrangements 1 and 2.
Let us make an additional construction as in $1^{\prime}$, Fig. 3, where $CC^{\prime}$ is tangent to the right circle at its common point with the concave side. Then all conditions of Lemma 2 are met for $\triangle ABC$, which implies that one can increase the total area by enlarging one of the circles in arrangement 1, i.e. there is a room for a local improvement, as a strictly convex function reaches its maximum at one of the end points. Thus, arrangement 1, Fig. 3, cannot be optimal. To see that arrangement 2 in Fig. 3 is not optimal, draw tangents to each circle at their common points with the concave side as in arrangement $2^{\prime}$, Fig. 3. Then again all conditions of Lemma 2 are met for $\triangle ABC$ in arrangement $2^{\prime}$, Fig. 3, which implies that there is a room for a local improvement. Thus, arrangement 2, Fig. 3, cannot be optimal. But since there must be an optimal arrangement by the celebrated Weierstrass maximum theorem, we conclude that any optimal arrangement must contain the incircle. This implies that the greedy arrangement is optimal. $\square$
Let us prove the result similar to Lemma 2 for convex quadrilaterals.
Lemma 3.
Let $ABCD$ be a convex quadrilateral with $A$ and $C$ being opposite vertices, and let $AA^{\prime}$ be a segment in it. Assume that two externally tangent circles are given such that the first circle touches either the side $AB$ or $AD$ and the interior of $AA^{\prime}$, and the second circle touches the sides $BC$ and $CD$. Then the radius of one of the circles, $r$, uniquely determines that of the other, $R(r)$, and, moreover, the function describing the sum of their areas is strictly convex with respect to $r$.
Proof.
We follow a strategy similar to the one used in proving Lemma 2 in [Andreatta et al.2011]. Let $r$ be the radius of the circle inscribed into $\angle BCD$. Without loss of generality, we may assume that the other circle touches $AD$ (see Fig. 4). It is easy to see that each such circle induces a unique circle in $\angle A^{\prime}AD$, which implies that we can obtain a functional relation between their radii. Let $R(r)$ be the radius of the circle in $\angle A^{\prime}AD$. We claim that $R(r)$ is midpoint convex. To see this, let us recall the following well known result: In any quadrilateral, the sum of the lengths of two opposite sides is at least twice the distance between the midpoints of the remaining two sides. As mentioned in [Andreatta et al.2011], the quadrilateral can be convex, concave, or self-intersecting, and can have collinear or even coinciding vertices.
Let $r_{1}$, $R(r_{1})$ and $r_{2}$, $R(r_{2})$ be the radii of two pairs of circles arranged as it is described in Lemma 3, and denote by $O_{1}$, $O^{\prime}_{1}$, and, similarly, by $O_{2}$, $O^{\prime}_{2}$ their centers (see Fig. 4).
Clearly, $|O_{1}O^{\prime}_{1}|=r_{1}+R(r_{1})$ and $|O_{2}O^{\prime}_{2}|=r_{2}+R(r_{2})$. Applying the above result to the quadrilateral $O_{1}O_{2}O^{\prime}_{2}O^{\prime}_{1}$ taking $O_{1}O^{\prime}_{1}$ and $O_{2}O^{\prime}_{2}$ as the opposite sides, and $M$ and $N$ as the midpoints of the two remaining sides, we get
| $\displaystyle|MN|\leq\frac{|O_{1}O^{\prime}_{1}|+|O_{2}O^{\prime}_{2}|}{2}=% \frac{r_{1}+r_{2}}{2}+\frac{R(r_{1})+R(r_{2})}{2}.$ |
It means that the circle of radius $\frac{r_{1}+r_{2}}{2}$ centered at $M$ and the circle of radius $\frac{R(r_{1})+R(r_{2})}{2}$ centered at $N$ are either externally tangent or overlap. Moreover, the first occurs if and only if the bisectors of $\angle A^{\prime}AD$ and $\angle BCD$ coincide. Thus,
| $\displaystyle R\left(\frac{r_{1}+r_{2}}{2}\right)\leq\frac{R(r_{1})+R(r_{2})}{% 2},$ |
and $R(r)$ is midpoint convex. Recall some basic results on convex functions, namely: (a) for a continuous function mid-point convexity implies convexity, and if the first is strict then so is the second; (b) if two real valued functions $f(x)$, $g(x)$ are convex, and at least one them is strictly convex, then $f(x)+g(x)$ is strictly convex; (c) if, in addition to being strictly convex, $f(x)$ is increasing, then $f(g(x))$ is strictly convex. According to [Niculescu and Persson2006], the first result was proven independently by H. Blumberg and W. Sierpiński under a weaker condition, whereas results (b) and (c) can be easily obtained [see, for example, Chap. 3.2 in [Boyd and Vandenberghe2004]]. Then we may conclude that the function $S(r)=\pi(r^{2}+{R(r)}^{2})$ is strictly convex with respect to $r$. $\square$
Let us call a circle contained in a semi-concave quadrilateral big if it touches at least three of its sides. Lemma 3 leads to the following result.
Theorem 2.
Let $n\leq 2$. Consider an arrangement of $n$ tangent circles in a semi-concave quadrilateral such that one of them is tangent to two adjacent sides of the quadrilateral. If such an arrangement is optimal, then at least one of the circles is big.
Proof.
When $n=1$, it is clear that an optimal circle must be big; the center of such circle is known as the Chebyshev center (see Chap. 8.5.1 in [Boyd and Vandenberghe2004]). Let $n=2$; by Lemma 1A, we should focus on rigid arrangements. It suffices to show that none of the rigid arrangements that satisfies the given description but has no big circle is optimal.
First, we claim that there are six combinatorially different such arrangements.
To see this, notice that, in such arrangement, each of the mutually tangent circles must touch two sides of the quadrilateral; otherwise, rigidity is violated. Since at least one of the circles is tangent to two adjacent sides, there are two possibilities: either (a) a circle is tangent to two adjacent straight sides, or (b) a circle is tangent to a straight side and the concave side adjacent to it. In Case (a) , the second circle can be tangent either to two adjacent straight sides (arrangement 1 in Fig. 5); or to a straight side and the concave side adjacent to it such that the straight side is common to both circles (arrangement 2 in Fig. 5); or the second circle is tangent to the third straight side and to the concave side (arrangement 3 in Fig. 5); or, finally, the second circle is tangent to the concave side and to the initial straight side opposite to the concave side (arrangement 4 in Fig. 5). Case (b) leads us to arrangements 2, 3, 5, and 6 in Fig. 5; namely that the second circle is located either in one of the three other corners, or it is tangent to the nonadjacent straight and concave sides. However, two out of these four arrangements are combinatorially identical to arrangements in Case (a) , and the remaining two arrangements are arrangements 5 and 6 in Fig. 5. This proves our claim.
For all arrangements in Fig. 5, except arrangement 3, one can directly apply Lemma 2 and make a similar argument as in the proof of Theorem 1 to show that there is a room for a local improvement. This then shows that none of arrangements 1, 2, 4, 5, or 6 in Fig. 5 is optimal. Regarding arrangement 3 in Fig. 5, let us make an additional construction shown in Fig. 6, where $AA^{\prime}$ is tangent to the top circle at its common point with the concave side.
Then all the conditions of Lemma 3 are met for the quadrilateral $ABCD$, which implies that one can increase the total area by enlarging one of the circles, i.e. there is a room for a local improvement. Thus, arrangement 3 can not be optimal either. $\square$
2.2 Solution to Malfatti’s Marble Problem
Let us now prove the following result.
Theorem 3.
[[Zalgaller and Los1994]] If $n=3$, the greedy arrangement solves Problem 1.
Proof.
By Lemma 1A, we need to consider only rigid arrangements. We proceed in four steps.
-
Step 1:
There are fourteen combinatorially different rigid arrangements.
It is shown in [Zalgaller and Los1994] that there are fourteen combinatorially different rigid arrangements as depicted in Figs. 7 and 8 below.
-
Step 2:
Let us analyze arrangements 1–5 in Fig. 7 .
We claim that if an arrangement is optimal, and one of the circles is the incircle, then it must be the greedy arrangement. To see this, assume that one of the circles is the incircle, and remove the region enclosed by this circle from the triangle. Then, by Lemma 1B, the remaining circles possess an optimal arrangement in the remaining region. Notice that the remaining region is a union of three non-overlapping semi-concave triangles.
There are two possibilities: either the remaining two circles are located in different semi-concave triangles, or they are located in the same semi-concave triangle. In each case, their allocation must be greedy by Theorem 1. Since, in the greedy arrangement, the first circle is always the incircle, our claim is established. This shows that, if there is an optimal arrangement in Fig. 7, then it must be the greedy one, which is either arrangement 1 or arrangement 2.
-
Step 3:
Let us analyze arrangements 11–14 in Fig. 8 .
Let us first apply the following procedure to arrangements 11–13 in Fig. 8. Take one of the circles which is tangent to two sides of the triangle, and remove the region enclosed by this circle. If the initial arrangement was optimal, then, by Lemma 1B, the remaining two circles must be arranged optimally in the remaining semi-concave quadrilateral. By Theorem 2, this implies that at least one of the remaining two circles must be big. Thus, we may conclude that arrangements 11–13 are not optimal.
For arrangement 14 in Fig. 8, let us draw three inner tangents to the circles as in Fig. 9. It is known that they intersect at the radical center of the circles, denoted by $O$.
Take any pair of circles; we claim that their inner tangent line intersects the sides of $\triangle ABC$ (or their extensions) to which the circles are tangent. To see this, consider the top two circles. It is clear that their inner tangent line intersects at least one of the sides $AB$ or $BC$. Assume, without loss of generality, that the tangent line intersects $BC$ at the point $N$. Let us show that $\measuredangle ONC<\measuredangle ABC$. Suppose, by contradiction, that $\measuredangle ONC\geq\measuredangle ABC$. If $\measuredangle ONC=\measuredangle ABC$, then one can displace the circle centered at $H$ toward $BC$ without affecting the other circles. This means that one can enlarge the circle centered at $F$ by moving it toward the point $A$, which contradicts rigidity (see Fig. 10a). If $\measuredangle ONC>\measuredangle ABC$, then one can enlarge the circle centered at $H$ by moving it toward point $B$, which also contradicts rigidity (see Fig. 10b).
Thus, we conclude that $\measuredangle ONC<\measuredangle ABC$, which implies that the rays $ON$ and $AB$ must intersect, and our claim is established. Then, points $P$ and $K$ are well defined, and applying Lemma 2 to $\triangle APK$, we conclude that the sum of the areas of the circles centered at $H$ and $F$ is subject to a local improvement, i.e. one can increase this sum without affecting the third circle. This, in turn, implies that arrangement 14 in Fig. 8 is not optimal.
-
Step 4:
Let us analyze arrangements 6–10 in Fig. 8 .
Proving the non-optimality of arrangements 6, 7, 8, and 10 is rather straightforward, see [Zalgaller and Los1994]. Here are the main ideas. Arrangement 6 in Fig. 8 is known as the Malfatti circles. Using explicit formulas for their radii, one can show that the sum of their areas is less than that in arrangement 1 in Fig. 7 (see p. 3166 in [Zalgaller and Los1994]). For arrangement 7 in Fig. 8, one can express the sum of the areas of the circles as a function of the radius of the top circle and show that it is strictly convex. Arrangement 8 in Fig. 8 is treated similarly, with the middle circle playing the role of the top circle in arrangement 7 [(see p. 3167 in [Zalgaller and Los1994]]. Finally, for arrangement 10 in Fig. 8, one can always reflect the middle circle with respect to the line connecting centers of the other two circles, and then enlarge its mirror image [(see p. 3175 in [Zalgaller and Los1994]]. Thus, arrangements 6, 7, 8, and 10 can not be optimal.
However, it is not easy to prove the non-optimality of arrangement 9 in Fig. 8. The proof in [Zalgaller and Los1994] can be outlined as follows. Consider arrangement 9 in Fig. 8 and draw three auxiliary circles centered at $S,Q,O$ as shown in Fig. 11.
Assume, by contradiction, that the circles centered at $O_{1},O_{2},O_{3}$ constitute an optimal arrangement. This implies that $\measuredangle A<\measuredangle B$; otherwise the circle centered at $Q$ is larger than the circle centered at $O_{3}$. In addition, the circle centered at $O_{3}$ must be at least as big as any of the three auxiliary circles. These statements, together with rigidity, put a narrow bound on the shape of $\triangle ABC$, as well as on the positions of the circles centered at $O_{1},O_{2},O_{3}$. [Zalgaller and Los1994] then used a computer to show that, within this range, the total area of the three circles in arrangement 9 in Fig. 8 is less than that in arrangement 1 in Fig. 7.
Final conclusion: From Steps 3 and 4, it is clear that Fig. 8 does not contain an optimal arrangement. Since, by the Weierstrass maximum theorem, there must be an optimal arrangement, this, together with Lemma 1A and Step 1, implies that Fig. 7 contains an optimal arrangement. Then, by Step 2, we may conclude that the greedy arrangement is optimal. $\square$
3 Some Related Extremum Problems
To prove and conjecture!
Paul Erdős
For any vector ${\mathbf{x}}\in\mathbb{R}^{n}$, let ${\mathbf{x}^{\prime}}\in\mathbb{R}^{n}$ be the vector obtained from ${\mathbf{x}}$ by reordering its components in a descending order. We say that ${\mathbf{x}}\in\mathbb{R}^{n}$ weakly majorizes ${\mathbf{y}}\in\mathbb{R}^{n}$, denoted as ${\mathbf{x}}\succeq{\mathbf{y}}$, if $\sum_{i=1}^{k}x^{\prime}_{i}\geq\sum_{i=1}^{k}y^{\prime}_{i}$ for all $k\in\{1,2,...,n\}$. Consider the following problem.
Problem 2.
Find an arrangement of $m\in\mathbb{N}$ circles in $\triangle ABC$ so that the sum of their radii is maximal.
The following result gives a direct connection between Problems 1 and 2.
Theorem 4.
Let $\triangle ABC$ be a given triangle in a plane, and let $n\in\mathbb{N}$ be a given number. If the greedy arrangement solves Problem 2 for all $1\leq m\leq n$, then it solves Problem 1.
Proof.
The following result is well known.
Lemma 4.
(Hardy-Littlewood-Pólya type inequality) Let ${\mathbf{x}},{\mathbf{y}}\in\mathbb{R}^{n}_{+}$ be such that ${\mathbf{x}}\succeq{\mathbf{y}}$. If $f:\mathbb{R}_{+}\rightarrow\mathbb{R}$ is an increasing and convex function, then $\sum_{i=1}^{n}f(x_{i})\geq\sum_{i=1}^{n}f(y_{i})$.
For a proof, see p. 92 in [Marshall et al.2011]. Let ${\mathbf{x}}=(r^{\star}_{1},...,r^{\star}_{n})\in\mathbb{R}^{n}_{+}$ be the vector of radii of $n$ circles arranged according to the greedy arrangement. Notice that, by definition, $r^{\star}_{1}>r^{\star}_{2}\geq...\geq r^{\star}_{n}$. Let ${\mathbf{y}}=(r_{1},...,r_{n})\in\mathbb{R}^{n}_{+}$ be the vector of radii of $n$ circles arranged arbitrarily. If there is any arrangement of $n$ circles in $\triangle ABC$, then any $k\leq n$ of them constitute an arrangement of $k$ circles in the same triangle. Then the condition that the greedy arrangement solves Problem 2 for all $1\leq m\leq n$ implies that ${\mathbf{x}}\succeq{\mathbf{y}}$. Since $f(r)=r^{2}$ is convex and increasing on $[0,\infty)$, by Lemma 4, we conclude that $\sum_{i=1}^{n}{r^{\star}_{i}}^{2}\geq\sum_{i=1}^{n}{r_{i}}^{2}$.$\square$
Notice that the objective function in Problem 2 is linear. Moreover, when $m\leq 2$, the solution of Problem 1 in [Andreatta et al.2011] directly applies to Problem 2. For $m=3$, the above solution of Problem 1 in Sect. 2 can be adapted to Problem 2 without much alteration if one makes the following observation: “the quadrilateral inequality that our proof is based on is strict when we restrict our attention to a triangular region, which, in turn, implies that, in a rigid arrangement, the sum of radii function is strictly convex.”
The analysis of all fourteen rigid arrangements in Problem 2, except arrangements 6 and 9 in Fig. 8, is the same as above. Only arrangements 6 and 9 need somewhat different approach. We should also note here that the idea of using majorization technique to connect optimization problems is rather classic, as stated in [Dahl and Margot1998]: “A general and important technique for finding inequalities in various fields is to discover some underlying majorization combined with a suitable Schur convex function.”
It is reported in [Andreatta et al.2011] that Melissen made the following conjecture in 1997.
Conjecture 1.
(Melissen) For all $n\in\mathbb{N}$, the greedy arrangement solves Problem 1.
The discussion above suggests that Problems 1 and 2 are likely to have the same solution. Probably, to solve Problem 2 is not much more difficult, if not easier, than to solve Problem 1, and Problem 2 also has broader implications. Therefore, it is natural to direct our attention to Problem 2, and update Conjecture 1 as
Conjecture 2.
For all $m\in\mathbb{N}$, the greedy arrangement solves Problem 2.
In the context of generalizing the Chebyshev center problem, [Enkhbat and Barsbold2013] studied the problem of inscribing two non-overlapping balls of the maximal total radii into a polytope. They formulated it as a bilevel programming problem, proposed a gradient based method, and demonstrated it by solving some test problems. Below, we show that there is a simple, elegant, and complete solution to this problem if we consider a certain class of polygons. From now on, we consider only convex polygons, and, as usual, a polygon is tangential if there is an inscribed circle that touches each of its sides, and two vertices of a tangential polygon are diagonally opposite if they are collinear with the incenter. Let us prove two useful lemmas.
Lemma 5.
Let $\omega$ be a circle, and $X$, $Y$ be two points disjoint from the region enclosed by $\omega$. Then any circle which passes through $X$ and $Y$ has an arc connecting these two points and disjoint from the region enclosed by $\omega$.
Proof.
An $XY$-circle is a circle that passes through the points $X$ and $Y$. An $XY$-line, $XY$-segment, and $XY$-arc are defined analogously. The plane is divided into two halves when we draw the $XY$-line. One of these halves we call the left half-plane, and the other one we call the right half-plane. It is well known (and can be easily proven) that locus of the centers of the $XY$-circles is the line perpendicular to the $XY$-segment, which divides each of the circles into two equal parts. We call this line the center line (see Fig. 12).
There are two cases: either $\omega$ intersects the $XY$-line, or it does not. If $\omega$ does not intersect the $XY$-line, we may assume, without loss of generality, that $\omega$ is located entirely in the left half-plane. Then, since every $XY$-circle has an $XY$-arc located in the right half-plane, this arc is disjoint from $\omega$ and its interior (see Fig. 13). Notice that this argument also applies if $\omega$ is tangent to the $XY$-line.
If $\omega$ intersects the $XY$-line, there are again two possibilities: either $\omega$ intersects the $XY$-segment, or it does not. Assume that $\omega$ intersects the $XY$-segment. Then, there are exactly two $XY$-circles which are internally tangent to $\omega$. The existence of these $XY$-circles is assured by solving celebrated Apollonius problem for the triple $X$, $Y$, and $\omega$. Let their centers be $O_{1}$ and $O_{2}$ (see Fig. 14).
For any $XY$-circle whose center is located to the left of $O_{1}$ (or $O_{2}$), its $XY$-arc belonging to the left half-plane is disjoint from $\omega$ and its interior, since such a circle can be obtained as a continuous image of transforming $O_{1}$ (or $O_{2}$) to the left along the center line. The same argument applies to show that for any $XY$-circle whose center is located to the right of $O_{1}$ (or $O_{2}$), its $XY$-arc belonging to the right half-plane is disjoint from $\omega$ and its interior.
Assume now that $\omega$ intersects the $XY$-line, but does not intersect the $XY$-segment. Without loss of generality, we may assume also that the center of $\omega$ is located in the left half-plane. Again, by solving Apollonius problem, we can find two $XY$-circles which are externally tangent to $\omega$. Let their centers be $O_{1}$ and $O_{2}$ (see Fig. 15).
Then:
-
•
If an $XY$-circle has a center located to the left of $O_{1}$, then its $XY$-arc lying in the right half-plane is disjoint from $\omega$ and its interior;
-
•
If an $XY$-circle has a center located to the right of $O_{2}$, then its $XY$-arc lying in the left half-plane is disjoint from $\omega$ and its interior; and
-
•
If an $XY$-circle has a center located between $O_{1}$ and $O_{2}$, then it is entirely disjoint from $\omega$ and its interior.
Thus, in all cases, for any $XY$-circle, there is an $XY$-arc which is disjoint from $\omega$ and its interior. This proves Lemma 5. $\square$
Lemma 6.
Let $k\geq 3$, and let us consider a tangential $k$-gon and a circle inscribed into it. Then the circle touches two nonadjacent sides of the polygon if and only if it is the incircle.
Proof.
First, notice that the incircle clearly touches two nonadjacent sides of the polygon. For the other direction, let $AB$ and $CD$ be the nonadjacent sides to which the circle is tangent. We denote the common points of $AB$ and $CD$ with the circle by $X$ and $Y$ respectively. Furthermore, let $O$ be the center of the incircle, and $O^{\star}$ be the center of the circle touching nonadjacent sides $AB$ and $CD$. It suffices to show that these two circles are concentric.
Suppose, by contradiction, that they are not concentric. Then both points $X$ and $Y$ must be outside the region enclosed by the incircle. By Lemma 5, this implies that there is an arc of the circle centered at $O^{\star}$ that connects $X$ and $Y$ and is disjoint from the region enclosed by the incircle. Since sides $AB$ and $CD$ are nonadjacent, there must be a section of the polygon that contains at least one of its sides and surrounds this arc (see the dashed sections in Fig. 16).
But that section cannot have any common points with the incircle since it is separated from it by the arc. On the other hand, the incircle must have a common point with every side of the polygon. Hence, we got a contradiction, and this proves Lemma 6.
Consider the following problem.
Problem 3.
Let $k\geq 3$. Find an arrangement of two circles in a tangential $k$-gon such that the sum of their radii is maximal.
We already know that the greedy arrangement solves Problem 3 for $k=3$. If the polygon is a square, it solves also the closely related problem of maximizing the sum of the areas of two circles, as shown in Problem 2.3.1 in [Andreescu et al.2006]. Our next result is as follows.
Theorem 5.
Let $k\geq 3$. Then the greedy arrangement solves Problem 3.
Proof.
By arguments similar to those in the proof of Lemma 1A, we can focus only on rigid arrangements. We claim that, in any such arrangement, there exist two circles that are mutually tangent, and each of them touches two adjacent sides of the polygon. To see this, suppose that these circles are not externally tangent. Then one can enlarge one of them by moving its center toward the incenter of the polygon, while keeping the other circle fixed (see Fig. 17a). This contradicts rigidity. Thus, we may assume that some two circles are mutually tangent.
Now suppose, by contradiction, that one of these circles (centered at $O_{1}$) does not touch any side of the polygon, and let $l$ be the inner tangent of the circles. As a consequence of the celebrated supporting hyperplane theorem [(see Chap. 2.5.2 in [Boyd and Vandenberghe2004]], $l$ divides the polygon into two small polygons, in one of which the circle centered at $O_{1}$ is inscribed in such a way that it touches only the side lying on $l$. Then the circle centered at $O_{1}$ can clearly be enlarged by moving its center along the direction orthogonal to $l$ until it touches another side of the polygon (see Fig. 17b). Since the other circle remains fixed throughout this enlargement, it contradicts rigidity. Thus, we may assume that each of the two mutually tangent circles is tangent to at least one side of the polygon.
Suppose, again by contradiction, that one of the circles (centered at $O_{1}$) is tangent to one side of the polygon ($AB$), but not to any of the two sides adjacent to this side. Draw the line $l$ described above. There are two possibilities: either $AB$ is not parallel to $l$, or it is. In the first case, one can enlarge the circle by moving its center along the bisector of the angle obtained by the intersection of $l$ with the line through $AB$ (see Fig. 18a). Such an enlargement is feasible as long as the circle does not touch any other side of the polygon, and it follows from Lemma 6 that this condition is indeed satisfied. But this enlargement does not affect the other circle; hence, it contradicts rigidity.
Now, let $AB$ be parallel to $l$. Then one can displace the circle centered at $O_{1}$ by moving its center in a direction parallel to $l$; the other circle remains unaffected by this displacement (see Fig. 18b). Again, Lemma 6 ensures that such displacement is feasible. After this, we obtain two disjoint circles, one of which is the same as one of the original two circles, while the other one is obtained from the other of the original two circles by a parallel translation. But as we already showed, if we have two disjoint circles, we can always enlarge them, which contradicts rigidity. This proves our claim.
Consider any rigid arrangement, and let $V$ and $F$ be the two vertices of the polygon such that each of them is the common end point of a pair of adjacent sides corresponding to this arrangement. There are two cases: either $V$ and $F$ are diagonally opposite, or they are not. In the first case, the sum of radii of the two circles is a linear function. To see this, observe that if $V$ and $F$ are diagonally opposite, their bisectors coincide, which implies that the points $O_{1},O_{1}^{\prime},O_{2},O_{2}^{\prime}$ are collinear (see Fig. 19a).
Then, the quadrilateral inequality is an equality, which implies that
| $R\left(\frac{r_{1}+r_{2}}{2}\right)=\frac{R(r_{1})+R(r_{2})}{2}.$ | (1) |
Equation (1) is called Jensen’s equality; it is known that any continuous function $R:[a,b]\rightarrow\mathbb{R}$ satisfying (1) is linear [(see p.43 in [Aczél1966]]. Since the sum of two linear functions is linear, this implies that our objective function $r_{1}+R(r_{1})$ is linear. Then, either it is a constant function, or it is not. In the first case, every point in its domain (which is a closed interval) is optimal; while in the second case, it attains its maximum at the end points of the domain. Thus, in either case, the greedy arrangement is optimal.
If $V$ and $F$ are not diagonally opposite, consider two circles whose centers lie on the bisectors of $\angle V^{\prime}VV^{\prime\prime}$ and $\angle F^{\prime}FF^{\prime\prime}$ (see Fig. 19b). Then one can repeat the argument in the proof of Lemma 3 to show that the function describing the sum of the radii of the two circles is strictly convex, which implies that any arrangement that does not contain the incircle is subject to a local improvement.33It suffices to observe that if $V$ and $F$ are not diagonally opposite, the quadrilateral inequality on which our proof is based is strict. Thus, the sum function is strictly convex. Thus, we may conclude that an optimal arrangement must contain the incircle. Then it must be the greedy arrangement. This proves Theorem 5. $\square$
Let us add few remarks on Theorem 5. First, in the light of Theorem 4, it should be clear that the greedy arrangement solves the problem of inscribing two circles into a tangential polygon with the maximum total area. However, as mentioned above, the objective function for the problem of the sum of the radii can be constant over rigid arrangements centered on the main diagonal (indeed, this is the case when we consider regular $2k$-gons). This implies that for this problem there can be optimal arrangements other than the greedy arrangement. But this is not the case for the problem of the maximization of the sum of the areas as it has a strictly convex objective function. This is one important aspect where these two problems differ.
Second, one might attempt to generalize Theorem 5 for more than two circles. However, the example in Fig. 20a gives an arrangement of three circles in a regular 12-gon, which resembles an Apollonian gasket, which has a larger sum of the radii than the greedy arrangement.44This construction is generic as it works for any $2k$-gon and, probably, for any $n>2$ circles. One might also look for a result analogous to Theorem 5 for cyclic polygons. But, again, there is a counterexample to such a claim (see Fig. 20b).
Finally, since a triangle is a tangential polygon, based on the above analysis, we suggest the following generalization of Conjecture 1.
Conjecture 3.
For all $n\in\mathbb{N}$ and $k\geq 3$, the greedy arrangement solves the problem of finding an arrangement of $n$ circles in a tangential $k$-gon with the maximal total area.
Notice that if we fix the radius of the incircle and let $k\rightarrow\infty$, we may think of the tangential polygon as a circle. Then, for any $n\in\mathbb{N}$, it is clear that the greedy arrangement is the only optimal solution for the problem of inscribing $n$ circles with the maximal total area into the limiting circle. This observation adds a credibility to Conjecture 3.
Acknowledgements
I am thankful to Chuluundorj Bekh-Ochir for initially proposing a version of Problem 2 to me, and to Purevsuren Damba for calling my attention to the Apollonius problem from the very beginning. I am also thankful to the other members of the Mathematics Department at the National University of Mongolia, and to Jan P. Boroński for stimulating discussions, and to the anonymous referee for helpful comments.References
- [Aczél1966] Aczél, J.: Lectures on Functional Equations and Their Applications. Academic, New York (1966)
- [Andreatta et al.2011] Andreatta, M., Bezdek, A., Boroński, J.P.: The problem of Malfatti: two centuries of debate. Math. Intell. 33(1), 72–76 (2011)
- [Andreescu et al.2006] Andreescu, T., Mushkarov, O., Stoyanov, L.: Geometric Problems on Maxima and Minima. Birkhäuser, Boston (2006)
- [Boyd and Vandenberghe2004] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)
- [Dahl and Margot1998] Dahl, G., Margot, F.: Weak $k$-majorization and polyhedra. Math. Program. 81(1), 37–53 (1998)
- [Enkhbat and Barsbold2013] Enkhbat, R., Barsbold, B.: Optimal inscribing of two balls into polyhedral set. In: Chinchuluun, A., Pardalos, P.M., Enkhbat, R., Pistikopoulos, E.N. (eds.) Optimization, Simulation and Control, pp. 35–47. Springer, Heidelberg (2013)
- [Goldberg1967] Goldberg, M.: On the original Malfatti’s problem. Math. Mag. 40(5), 241–247 (1967)
- [Lob and Richmond1930] Lob, H., Richmond, H.W.: On the solution of Malfatti’s problem for a triangle. Proc. Lond. Math. Soc. 30(2), 287–304 (1930)
- [Marshall et al.2011] Marshall, A.W., Olkin, I., Arnold, B.C.: Inequalities: Theory of Majorization and Its Applications, 2nd edn. Springer, Heidelberg (2011)
- [Niculescu and Persson2006] Niculescu, C., Persson, L.-E.: Convex Functions and their Applications: A Contemporary Approach. Springer, Heidelberg (2006)
- [Szabó et al.2007] Szabó, P.G., Markót, M.C., Csendes, T., Specht, E., Casado, L.G., García, I.: New Approaches to Circles Packing in a Square. Springer, Heidelberg (2007)
- [Zalgaller and Los1994] Zalgaller, V.A., Los, G.A.: The solution of Malfatti’s problem. J. Math. Sci. 74(4), 3163–3177 (1994)
