1 Introduction

In 1803 Italian mathematician Malfatti posed the following problem: how to pack three non-overlapping circles of maximum total area in a given triangle?

Malfatti originally assumed that the solution to this problem are three circles inscribed in a triangle such that each circle tangent to other two and touches two sides of the triangle.

Now it is well known that Malfatti’s solution is not optimal. There are works devoted to solving Malfatti’s problem [1–8]. The most common methods used for finding the best solutions to Malfatti’s problem were algebraic and geometric approaches. In 1994 Zalgaller and Los [3] showed that the greedy arrangement is the best one. Based on trigonometric equations and inequalities, using so called rigid systems they have found the best solution to Malfatti’s problem. It is seems that there is a little attention paid to Malfatti’s problem so far from a view point of optimization theory and algorithm. Aim of this paper is to fulfill this gap. The paper is organized as follows. In Sect. 2, we formulate Malfatti’s problem as the convex maximization problem. Global optimality conditions for Malfatti’s problem are given in Sect. 3. Section 4 is devoted to computational results.

2 Malfatti’s problem and convex maximization

In order to formulate Malfatti’s problem as an optimization problem, we need to do following steps.

First, we equivalently formulate the problem in terms of convex sets such as a ball and triangle set. Secondly, we characterize inscribed conditions of balls into a triangle set. For this purpose, we introduce the following sets. Denote by B(x, z) a ball with a center \(x\in \mathbb {R}^2\) and a radius \(z \in R\):

$$\begin{aligned} B(x,z) = \left\{ y\in \mathbb {R}^2 | \Vert y - x\Vert \le z \right\} , \end{aligned}$$
(1)

A triangle set \(D \subset \mathbb {R}^2 \) is given by

$$\begin{aligned} D = \left\{ x\in \mathbb {R}^2 | \langle a^i,x\rangle \le b_i,\quad a^i \in \mathbb {R}^2,\quad b_i \in \mathbb {R},\quad i = 1, 2, 3 \right\} , \end{aligned}$$
(2)

here \(\langle ,\rangle \) denotes the scalar product of two vectors in \(\mathbb {R}^2\), and \(\Vert \cdot \Vert \) is Euclidean norm, \(a^i\nparallel a^j,\; i\ne j;\; i,j=1,2,3\).

Theorem 1

\(B(x,z) \subset D\) if and only if

$$\begin{aligned} \langle a^i, x\rangle + z\Vert a^i\Vert \le b_i,\quad i = 1,2,3 \end{aligned}$$
(3)

Proof

Necessity Let \(y\in B(x,z)\) and \(y \in D\). A point \(y \in B(x,z)\) can be easily presented as \(y = x + zh, h \in \mathbb {R}^2, \Vert h\Vert \le 1.\) Condition \(y \in D \) follows that \(\langle a^i,y\rangle \le b_i, i=1,2, 3 \) or equivalently, \(\langle a^i,x\rangle + z\langle a^i,h\rangle \le b_i,i = 1,2,3,\quad \forall h \in \mathbb {R}^2\). Hence, we have

$$\begin{aligned} \langle a^i,x\rangle + z \max \limits _{\Vert h\Vert \le 1}\langle a^i,h\rangle \le b_i,\quad i = 1,2, 3 \end{aligned}$$

or

$$\begin{aligned} \langle a^i,x\rangle + z \langle a^i,\frac{a^i}{\Vert a^i\Vert }\rangle \le b_i,\quad i = 1,2,3, \end{aligned}$$

which yield

$$\begin{aligned} \langle a^i,x\rangle + z \Vert a^i\Vert \le b_i,\quad i = 1,2,3. \end{aligned}$$

Sufficiency Let condition (3) be held and on the contrary, assume that there exists \(\tilde{y} \in B(x,z)\) such that \( \tilde{y} \not \in D \). Clearly, there exists \(\tilde{h} \in \mathbb {R}^2 \) so that \(\tilde{y} = x + z \tilde{h}, \Vert \tilde{h} \Vert \le 1\). Since \(\tilde{y} \not \in D\), there exists \(j \in \{1,2,3\}\) for which \(\langle a^j, \tilde{y}\rangle > b_j\) or \(\langle a^j, x + z\tilde{h} \rangle = \langle a^j,x\rangle + z \langle a^j,\tilde{h} \rangle > b_j\).

On the other hand, we have \(\langle a^j, x \rangle + z \Vert a^j\Vert > b_j\) which contradicts (3).

Now we formulate inscribed conditions of three balls into a triangle set. Assume that intersections of interiors of these balls are empty. There are three main cases:

Case 1

Three balls are mutually tangent to each other.

Case 2

One of the balls is tangent to other two and the centers of the balls lie on the same line.

Case 3

One of the balls is tangent to other two but their centers don’t lie on the same line. At the same time, the last two balls don’t intersect with each other.

Denote by \(u(x_1,x_2),\,v(x_4,x_5)\) and \(p(x_7,x_8)\) centers of three balls inscribed in a triangle set D given by (2). Let \(x_3,\,x_6\) and \(x_9\) be their corresponding radii.

Now we are ready to formulate Malfatti’s problem for Case 1.

$$\begin{aligned}&\max f = \pi (x_3^2 + x_6^2 + x_9^2), \end{aligned}$$
(4)
$$\begin{aligned}&\langle a^i,u\rangle + x_3 \Vert a^i\Vert \le b_i,\quad i=1,2,3, \end{aligned}$$
(5)
$$\begin{aligned}&\langle a^i,v\rangle + x_6 \Vert a^i\Vert \le b_i,\quad i=1,2,3, \end{aligned}$$
(6)
$$\begin{aligned}&\langle a^i,p\rangle + x_9 \Vert a^i\Vert \le b_i,\quad i=1,2,3,\end{aligned}$$
(7)
$$\begin{aligned}&(x_4 -x_1)^2 + (x_5 -x_2)^2 = (x_3 + x_6)^2,\end{aligned}$$
(8)
$$\begin{aligned}&(x_7 -x_1)^2 + (x_8 -x_2)^2 = (x_3 + x_9)^2, \end{aligned}$$
(9)
$$\begin{aligned}&(x_7 -x_4)^2 + (x_8 -x_5)^2 = (x_6 + x_9)^2,\end{aligned}$$
(10)
$$\begin{aligned}&x_3 \ge 0,\quad x_6\ge 0,\quad x_9 \ge 0. \end{aligned}$$
(11)

The function f in (4) denotes a total area of the three balls. Conditions (5)–(7) characterize inscribed conditions of three balls into a triangle set while conditions (8)–(11) correspond to Case 1. We can easily see that conditions (8) and (9) and

$$\begin{aligned} (x_7 -x_4)^2 + (x_8 -x_5)^2 = (x_6 + 2x_3 + x_9)^2 \end{aligned}$$
(12)

describe Case 2. Case 3 is defined by conditions (8) and (9) and

$$\begin{aligned} (x_7 -x_4)^2 + (x_8 -x_5)^2 \ge (x_6 + x_9)^2. \end{aligned}$$
(13)

\(S_1\) denotes the set defined by the conditions (5)–(11).

\(S_2\) denotes the set given by the conditions (5)–(9), (11) and (12).

Meanwhile, \(S_3\) denotes the set given by conditions (5)–(9), (11) and (13).

The set \(S_1,\,S_2\) and \(S_3\) are nonconvex compact sets. Thus, problem (4)—(11) becomes the convex maximization problem over a nonconvex set. A stationary point of this problem satisfies a system of 36 equations and inequalities with 24 variables including Lagrange multipliers.

3 Global optimality conditions and algorithm

In previous section, we note that the solution to Malfatti’s problem is \(f^* = \max \{\max \nolimits _{x\in S_1} f\), \(\max \nolimits _{x\in S_2} f, \max \nolimits _{x\in S_3} f\}.\) Let us consider again these problems

$$\begin{aligned} \max \limits _{x\in S_i} f, S_i \subset \mathbb {R}^9,\quad i=1,2,3. \end{aligned}$$
(14)

Problems (14) belong to a class of concave programming or equivalently, convex maximization problem.

Global Optimality conditions for the convex maximization problem first formulated by Strekalovsky [9]. Now we apply this result to problem (14) as follows:

Theorem 2

[9] Let \(z\in S_i\) satisfy \(f'(z) \ne 0\), then z is a solution to problem (14) if and only if

$$\begin{aligned} \langle f'(y),x-y\rangle \le 0\quad \hbox { for all }\, y \in E_{f(z)}(f) \quad \hbox { and }\quad x \in S_i, \end{aligned}$$

where \(E_c(f) = \{ y\in \mathbb {R}^n | f(y) = c\}\) is the level set of f at c and \(f'(y)\) is the gradient of f at y.

Before presenting an algorithm for solving problem (14) it is useful to restate Theorem 2 in a convenient way via the function \(\varTheta (z)\) defined for \(z \in S_i\):

$$\begin{aligned} \varTheta (z) = \max \limits _{y\in E_{f(z)}(f)}\varPi (y), \end{aligned}$$

where \(\varPi (y)=\max \nolimits _{x\in S_i}\langle f'(y),x-y\rangle \).

It has been shown in [10] that the function \(\varPi (y)\) is continuous and differentiable in directions. Since f is strongly convex the set \(E_{f(z)}(f)\) is compact. Thus, \(\varTheta (z) < +\infty \). We note that \(\varPi (y) \le \varTheta (z)\) for all \(y\in E_{f(z)}(f)\).

Theorem 3

Let \(z\in S_i\) satisfy \(f'(z) \ne 0\), if \(\varTheta (z) = 0\) then z is a global solution to problem (14).

Proof

follows from the following inequalities:

$$\begin{aligned} \langle f'(y),x-y\rangle \le \varPi (y)=\max \limits _{x\in S_i}\langle f'(y),x-y\rangle \le \varTheta (z) = 0 \end{aligned}$$

which hold for all \(x\in S_i\) and \(y\in E_{f(z)}(f).\) \(\square \)

Now we apply the Algorithm MAX in [10] to solve problem (14) numerically.

figure a

The convergence of the Algorithm is given by the following theorem.

Theorem 4

[10] The sequence \(\{x^k, k = 1,2,\ldots \}\) generated by Algorithm MAX is a maximizing sequence for problem (14),that is,

$$\begin{aligned} \lim _{k\rightarrow \infty } f(x^k) = \max \limits _{x\in S_i}f(x), \end{aligned}$$

and every accumulation point of the sequence \(\{x^k, k = 1,2,\ldots \}\) is a global maximizer of the problem.

4 Computational results

Algorithm MAX starts with an arbitrary local maximizer \(x^k\) found by fmincon in Matlab. Note that in numerical experiments we solved subproblems \(\max \nolimits _{y\in E_{f(x^k)}(f)}\varPi (y)\) at each iterations \(k = 1,2,\ldots \), as problems with the single equality constraint by the set covering method [11] while problems \(\max \nolimits _{x\in S_i}\langle f'(y^k), x - y^k\rangle \) have been solved by Lagrangian method. For a test purpose, the triangle with vertices \(A(0,0),\,B(3,4)\) and C(8, 6) has been considered. As we can see in Sect. 2 that solving Malfatti’s problem consisted of three main cases. Then for Case 1 we have the following problem:

$$\begin{aligned}&\max f = \pi (x_3^2 + x_6^2 + x_9^2), \end{aligned}$$
(15)
$$\begin{aligned}&-\,4x_1 + 3x_2 + 5x_3 \le 0, \nonumber \\&\quad 6x_1 - 8x_2 + 10x_3 \le 0, \nonumber \\&\quad -\,2x_1 + 5x_2 + \sqrt{29}x_3 \le 14, \nonumber \\&\quad -\,4x_4 + 3x_5 + 5x_6 \le 0, \nonumber \\&\quad 6x_4 - 8x_5 + 10x_6 \le 0, \nonumber \\&\quad -\,2x_4 + 5x_5 + \sqrt{29}x_6 \le 14, \nonumber \\&\quad -\,4x_7 + 3x_8 + 5x_9 \le 0, \nonumber \\&\quad 6x_7 - 8x_8 + 10x_9 \le 0, \nonumber \\&\quad -\,2x_7 + 5x_8 + \sqrt{29}x_9 \le 14, \nonumber \\&\quad (x_4 -x_1)^2 + (x_5 -x_2)^2 - (x_3 + x_6)^2 = 0, \nonumber \\&\quad (x_7 -x_1)^2 + (x_8 -x_2)^2 - (x_3 + x_9)^2 = 0, \nonumber \\&\quad (x_7 -x_4)^2 + (x_8 -x_5)^2 - (x_6 + x_9)^2 = 0, \nonumber \\&\quad x_3 \ge 0,\quad x_6\ge 0,\quad x_9\ge 0. \end{aligned}$$
(16)

For Case 2, we replace 12th constraint in (16) with the following constraint:

$$\begin{aligned} (x_7 -x_4)^2 + (x_8 -x_5)^2 = (x_6 + 2x_3 + x_9)^2. \end{aligned}$$

Also, for Case 3 instead of 12th constraint in (16), we have the following constraint:

$$\begin{aligned} (x_7 -x_4)^2 + (x_8 -x_5)^2 - (x_6 + x_9)^2 \ge 0 \end{aligned}$$
(17)

In the computational experiment, from a view point of geometric triviality, we did not consider cases where at least one ball is not tangent to other two.

The performance of the proposed algorithm was tested on three cases of Malfatti’s problem. For a given triangle set, the programming code for the algorithm was written in Matlab and run on a computer Pentium Core 2. The results are given for each case in Table 1.

Table 1 Numerical results
Full size table

The global solution to Malfatti’s problem (15)–(16) corresponding to Case 3 was \(f^* = 3.192752\) and the centers of the balls were:

$$\begin{aligned} (x_1^*,x_2^*)= & {} (2.5830,2.5830),\\ (x_4^*,x_5^*)= & {} (3.4339,3.4339),\\ (x_7^*,x_8^*)= & {} (4.4925,4.0288). \end{aligned}$$

During computational process, totally 33 local and stationary points were examined by Algorithm MAX. Geometric pictures showing global solutions of 3 cases are given in Figs. 1, 2 and 3.

Fig. 1
figure 1

Case 1

Full size image
Fig. 2
figure 2

Case 2

Full size image
Fig. 3
figure 3

Case 3

Full size image

5 Conclusion

200 years old Malfatti’s problem, for the first time, has been examined from a point of global optimization theory and algorithm view. The problem was reduced to the convex maximization problem with 9 variables. The global optimality conditions by Strekalovsky as well as a global search algorithm in [9] have been applied to the problem. This approach gives us an opportunity to generalize Malfatti’s problem for a high dimensional polyhedral set which will be discussed in a next paper.