Extended General Malfatti’s Problem

Abstract

Malfatti’s problem involves three circles (called Malfatti circles) that are tangent to each other and two sides of a triangle. In this study, our objective is to extend the problem to find 6, 10, … $\sum _1^{n}i$ (n > 2) circles inside the triangle so that the three corner circles are tangent to two sides of the triangle, the boundary circles are tangent to one side of the triangle, and four other circles (at least two of them being boundary or corner circles) and the inner circles are tangent to six other circles. We call this problem the extended general Malfatti’s problem, or the Tri(T_n) problem, where Tri means that the boundary of these circles is a triangle, and T_n is the number of circles inside the triangle. In this paper, we propose an algorithm to solve the Tri(T_n) problem.

1. Introduction

Malfatti’s problem, as originally stated in 1803, was used to carve three circular columns from a triangular prism of marble to minimize waste. Equally, the problem poses the fitting of three circles into a given triangle such that the sum of their areas is the maximum possible. Malfatti erroneously believed that the solution was provided by three inscribed circles that are tangent to each other and tangent to the sides of the triangle. An instance of this problem is shown in Figure 1.

Since then, this second problem (circle tangency problem), which Malfatti believed maximizes the area (maximum area problem), has become understood as Malfatti’s problem in the literature. There are several known solutions to Malfatti’s problem. Fukagawa and Pedoe [1] mentioned that the general Malfatti’s problem for triangles was actually formulated and solved by Chokuen Ajima. Readers should refer to [2,3,4] for a history of the problem and an explanation of its various solutions and generalizations.

Malfatti’s problem involves finding three circles for an arbitrary triangle, and our objective is to extend the number of circles from three circles to T_n = $\sum _1^{n}i$, n = 1, 2, …. circles inside the triangle, with tangency properties among the circles and three sides of the triangles. We refer to the problem of T_n circles as the Tri(T_n) problem. Under this definition, the general Malfatti’s problem is the Tri(T₂) problem, and the Tri(T₁) problem asks us to find the inscribed circle of a triangle.

There are four sections in this paper. Section 1 and Section 2 illustrate Malfatti’s problem as well as the extended Malfatti’s problem. Section 3 provides a definition and theorem to support the proposed algorithms to solve the Tri(T_n) problem. The algorithm and execution result are illustrated in Section 4. Section 5 describes the implementation of this problem in more detail, as well as its potential applications. Section 6 presents our conclusion.

2. Problem Description and Algorithm to Solve Tri(T_n) Problem

In this section, we provide some terms to simplify the description of this problem (Section 2.1) and analyze the problem algebraically (Section 2.2).

2.1. Problem Description

In this paper, we define a triangle with three vertices, A, B, and C, and its associated angles are ∠A, ∠B, ∠C. The side lengths, opposite to the vertices A, B, and C, are a, b, and c, respectively. Furthermore, we define the coordinates for these three vertices, A = (x₁,y₁), B = (x₂,y₂), and C = (x₃,y₃), in a Cartesian coordinates system.

We aim to find T_n circles inside this triangle with tangency properties, as shown in Figure 2. In this figure, r_i,j denotes the radius of the circle, and its associated circle is C_i,j. In the Tri(T₁) problem, our objective is to find a circle inside a triangle and tangent to three sides of the triangle, which involves finding the incircle of the triangle. The Tri(T₂) problem is identical to Malfatti’s problem. In the Tri(T₃) problem, the aim is to find six circles; their tangency properties are shown in Figure 13b. We can similarly define the Tri(T₄) (as shown in Figure 13c) and the Tri(T_n) problems (as shown in Figure 2).

In Figure 2, among these T_n = $\sum _1^{n}i$ circles, we define the circles that are tangent to two sides of the triangle as the corner circles and the circle that is tangent to one side of the triangle as the boundary circle. The circles that are not tangent to any side of the triangle are called the inner circles. Note that all problems except Tri(T₁) have three corner circles (C_1,1, C_n,1, C_n,n) and have 3(n − 2), n > 1 edge circles. There are (n − 2)(n − 3)/2, n > 2 inner circles. It should also be noted that there is no inner circle when n = 1, 2, 3 and no boundary circle when n = 1, 2.

There are tangency relations among all circles inside the triangle, as shown in the tangency graph for all circles (see Figure 3a). In the graph for the circles in the Tri(T_n) problem, the vertices represent circles, and the edge connecting two vertices represents the external tangency relation between these two circles. The circle C_i,j, i = 2, …, n, j = 1, …, i − 1, (with radius r_i,j) is tangent to the next circles C_i,j+1 in the same row, and tangent to the circle in the next row C_i+1,j and C_i+1,j+1, for i = 1, …, n − 1, j = 1, …, i in the next row. Figure 3a is an example of the tangency relations for T₄ = 10 circles inside the triangle. Besides the tangency property among circles, some circles are also tangent to the sides of the triangle. To add the tangency relation between the circle and the side of the triangle, we added a triangle to surround these circles and an edge to connect the vertex that represents a circle to the sides of the triangle; an example for T₄ is shown in Figure 3b. Note that the tangency graph is a helpful tool for knowing the tangency relation among the circles and sides of the triangle, but it is not a solution to our problem because we do not know the circle centers and radii for all circles yet. Therefore, the Figure 3b is a tangency graph for the Tri(T₄) problem. And, given the coordinates of the three vertices of a triangle, the associated solution is shown in Figure 13c.

2.2. Algebraic Analysis of the Problem

We can approach Malfatti’s problem (see Figure 1) in the following way:

• Let C_i = (x_i,y_i,r_i) represent a circle whose center and radius are (x_i,y_i) and r_i, respectively; i = 1, 2, 3. L₁, L₂, L₃ are three lines for the triangle. Circle C₁ is tangent to lines L₂ and L₃. Circle C₂ is tangent to lines L₁ and L₃, and Circle C₃ is tangent to lines L₁ and, L₂.
• Generate the equations for the “circle/side” tangency relation carefully. For example, circle C₃ is tangent to line L₁. The equation can be generated by computing the distance from (x₃,y₃) to line L₁ is equal to r₃. The line equation we generate, ax + by + c = 0, has the properties that all points (x_i,y_i) inside the triangle have the property that ax_i + by_i + c > 0, i = 1, 2, 3 (detailed explained below). Therefore, we generate six equations because every circle is tangent to two sides of the triangle. Note that the equations are degree-one equations.
• Generate the equations for the “circle/circle” tangency relation. For example, circle C₁ is tangent to C₂. The equation can be generated by computing the distance between two centers, which is equal to the sum of their radii. There are three equations generated in this case. Note that when we want to eliminate the square root of the distance function, it becomes a degree-two polynomial.

We generate six degree-one (details explained below) and three degree-two polynomials. It probably can be solved by a Computer Algebra package, such as Maple [5] or SymPy [6], in this case. However, When n increases, the number of equations grows quadratically. Using SymPy to implement the above approach, it is easy to solve the Tri(T₁) problem because we generate three linear equations with three variables. However, when we go to the Tri(T₂) problem, we generate six linear equations and three quadratic equations. The program runs for a long time without a solution or any error message. Therefore, we stop using a symbolic approach to solve the Tri(T_n) problem when n > 1.

Regarding how to generate the degree-one equation in step two, we use a directed line, or ray, to generate the equation. Let v₁ = (x₁,y₁), v₂ = (x₂,y₂), v₃ = (x₃,y₃) be the vertices of the triangle, rotated counterclockwise. Consider the ray from v₁ to v₂, the equation for this ray is ax + by + c = 0, where a = y₁ − y₂, b = x₂ − x₁, c = x₁y₂ − x₂y₁. Using this formula, the ray from v₂ to v₁ will be −ax − by − c = 0. Furthermore, the points (x₃,y₃) on the left part of the ray have the property ax₃ + by₃ + c > 0. Both rays from v₁ to v₂ and from v₂ to v₁ represent the same line. The equation for the constraint with the circle center (x₃,y₃) and radius r₃, which is tangent to the ray ax + by + c=0, is $\mathrm{a}{x}_3+b{y}_3+c-r_3\sqrt{a^2+b^2}=0$. This is because a, b, c are real numbers; this is a degree-one equation with variables x₃, y₃, and r₃.

In the Tri(T_n) problem, we have 3T_n variables. There are 3n equations generated by the “circle/side” tangency relation and the 3T_n−1 ”circle/circle” tangency relation. If we want to solve the Tri(T₃), Tri(T₄), Tri(T₈), and Tri(₃₀) problems, for which the solutions are shown in Figure 13, the system of equations will have 18, 30, 108, and 1395 equations. Based on the quadratic growth of the number of equations and our experience regarding the Tri(T₂) problem, this is not an effective way to solve the problem. We searched for a mathematical solution from other researchers for Tri(T₁) and Tri(T₂) and proposed an algorithm to solve the Tri(T_n) problem Tri(T_n) for n > 2.

3. Definition and Theorem for the Tri(T_n) Problem

Let us start with the Tri(T₁) and Tri(T₂) problems. These two problems can be solved directly using a mathematic equation, as described in Section 3.1 and Section 3.2.

3.1. The Tri(T₁) Problem

In this problem, we aim to find a circle tangent to three sides of a triangle. We can use the formula for the inscribed circle to solve the problem. The formula is

Theorem 1

([7]). The inscribed center is at (x,y) = ((aA + bB + cC)/(a + b + c) with radius r = $\sqrt{{\displaystyle \frac{\left(s-a\right)\left(s-b\right)\left(s-c\right)}{s}}}$, where s = (a + b + c)/2.

Considering a = b = c or a = b, it is easy to establish the following corollaries (evidence in Theorem 1):

Corollary 1.

Consider an equilateral triangle with side length a, its inscribed circle centered at (A + B + C)/3 with radius${\displaystyle \frac{\mathit{a}}{\mathbf{2}\sqrt{\mathbf{3}}}}$.

An isosceles triangle is a triangle that has at least two sides of equal length. Let us call these two sides the legs of the isosceles and the other side the base of the triangle, then

Corollary 2.

Consider an isosceles triangle whose leg and base lengths are a and c, respectively. Its inscribed circle is centered at (x,y) = [a(A + B) + cC]/(2a + c) with radius r = ${\displaystyle \frac{\mathit{c}}{\mathbf{2}}}\sqrt{{\displaystyle \frac{\mathbf{2}\mathit{a}\mathbf{-}\mathit{c}}{\mathbf{2}\mathit{a}\mathbf{+}\mathit{c}}}}$.

3.2. The Tri(T₂) Problem

We aim to find three circles inside a triangle that are tangent to each other pairwise, and every circle is tangent to two sides of the triangle.

There are formulae to solve this problem. These formulae were discovered by Malfatti and published in 1811 [8].

Theorem 2

([3,8]). The radii of the Malfatti circles are

$${\mathrm{r}}_1={\displaystyle \frac{r}{2(s-a)}}(s-r+d-e-f)$$

(1)

$${\mathrm{r}}_2={\displaystyle \frac{r}{2(s-b)}}(s-r-d+e-f)$$

(2)

$${\mathrm{r}}_3={\displaystyle \frac{r}{2(s-c)}}(s-r-d-e+f)$$

(3)

where s = (a + b + c)/2, r = $\sqrt{{\displaystyle \frac{(s-a)(s-b)(s-c)}{s}}}$ is the radius of the inscribed circle, and d, e, and f is the distance from the center of the inscribed circle to A, B, and C, respectively.

The values r₁, r₂, and r₃ are the radii of the circles near vertices A, B, and C, respectively. Notice that when we find the radii of these three circles (for example, r₁), the center of these circles is easy to find from the location of the vertex (A), angle bisectors (of ∠A), and radius (r₁). We provide a simple example for finding the inscribed circle and Malfatti’s circle.

Example 1.

Consider a triangle whose vertices are A = (−8,−7), B = (6,−2), and C = (9,8). From theorem 1, we find the inscribed center (x,y) = (3.88, 0.01), with a radius of 2.61, as shown in Figure 4a. The centers of three Malfatti circles located at (1.99, −1.01), (5.18,−1.22), and (5.03, 1.80) with radii 2.29, 1.01, and 2.02, respectively, are shown in Figure 4b.

Using a = b = c or a = b, we establish the following corollaries (proof by Theorem 2):

Corollary 3.

The radii of the three Malfatti circles for the equilateral triangle with side length a have the same value r₁ = r₂ = r₃ =${\displaystyle \frac{3-\sqrt{3}}{2}}$ r =  ${\displaystyle \frac{\sqrt{3}-1}{4}}$a.

Corollary 4.

Consider an isosceles triangle whose leg and base lengths are a and c, respectively. Its inscribed circle is centered at (x,y) = [a(A + B) + cC]/(2a + c) with radius r = ${\displaystyle \frac{c}{2}}w$, where w = $\sqrt{{\displaystyle \frac{2a-c}{2a+c}}}$, The three Malfatti circles for this triangle have radii r₁ = r₂ = (2a + c)w(1 − w)/4 r₃ = c[${\displaystyle \frac{1}{4w}}$ + ${\displaystyle \frac{w^2}{4}}$ − ${\displaystyle \frac{c}{2a+c}}\sqrt{{\displaystyle \frac{a}{2a-c}}}$].

Note that the variables r, d, e, f can be represented by the constant w where r = ${\displaystyle \frac{c}{2}}$w, d = e = $\sqrt{{\displaystyle \frac{a}{2a-c}}}$cw, f = aw, and when a = c, the result for Corollary 4 is the same as that for Corollary 3.

When the angle opposite to the base is 2θ, we have sin(θ) = c/2a. Assume that T = tan(${\displaystyle \frac{\theta }{2}}$), Corollary 4 can be rewritten as

Corollary 5.

Consider an isosceles triangle whose leg and base lengths are a and c, respectively. The angle opposite to the side with length c is 2θ. The three Malfatti circles for this triangle have radii r₁ = r₂ = s${\displaystyle \frac{2T(1-T)}{1+T^2}}$, r₃ = ${\displaystyle \frac{c}{2{\left(1+T\right)}^2\left(1-T\right)}}\left(3T^2-2\sqrt{2}T\sqrt{1+T^2}+1\right)$ where s = (2a + c)/2, T = tan(${\displaystyle \frac{\theta }{2}}$).

Let us give an example of finding the Malfatti circles of an isosceles triangle and observe the result.

Example 2.

Consider an isosceles triangle whose leg and base lengths are l = 10 and b = 12, respectively. The radii for the Malfatti circles are r₁ = r₂ = 2.0, r₃ = 1.718, as shown in Figure 5a. Let (l,b) = (10, 8), the radii for the Malfatti circles are r₁ = r₂ = 1.583, r₃ = 1.827, as shown in Figure 5b. We observe that when the length of leg l = $\sqrt{{\left({\displaystyle \frac{b}{2}}\right)}^2+h^2}$ < b (as in Figure 5a), r₁ = r₂ < r₃. Additionally, when l > b, r₁ = r₂ > r₃. It is easy to guess that when l = b, the isosceles triangle becomes an equilateral triangle, so that r₁ = r₂ = r₃. Let l = b = 10, r₁ = r₂ = r₃ = 1.830.

In the Tri(T₃) problem, we aim to find six circles inside the triangle satisfied by constraints specified by its tangency graph. The three circles tangent to two sides of the triangle are known as corner circles. Furthermore, each of the other three circles is tangent to each other, and it is also tangent to one side of the triangle and the two corner circles. We did not find any simple mathematical solution for the Tri(T₃) problem. However, this problem has been solved using an algorithm with excellent performance. Chiang, Hoffmann, and Rosen [9] proposed algorithms to solve the classical Malfatti’s problem and the Tri(T₃) problem. In the Tri(T₃) problem, the isosceles case can also use a depth buffer to extract the solution, and for other triangles, the idea of an inverse construction and angle locking has been introduced in the algorithm to solve the Tri(T₃) problem. Please see Reference [9] for details.

3.3. The Tri(T_n) Problem, n > 2

In this paper, we propose an algorithm to solve the Tri(T_n), n > 2 problems. Before illustrating the algorithm, we will provide terms and theorems to support it.

There are some theorems we need to derive before we propose the algorithm.

Theorem 3.

Three circles C, C₀, C₁ are tangent to each other with radii r, r₀, and r₁. The angle α between two vectors, from the center of C to center of C₀, and from center of C to center of C₁, as shown in Figure 6, is equal to cos⁻¹${\displaystyle \frac{r^2+\left(r_0+r_1\right)r-r_0{r}_1}{(r+r_0)(r+r_1)}}$.

Proof of Theorem 3.

Consider the triangle whose sides are the line segments connecting the centers of three circles. We know the length of the triangle sides are r + r₀, r + r₁, and r₁ + r₂. From the cosine theorem, we have (r₀ + r₁) = (r + r₀) + (r + r₁) − 2(r + r₀)(r + r₁)cos(α). Therefore, the angle α is equal to cos ${\displaystyle \frac{r^2+\left(r_0+r_1\right)r-r_0{r}_1}{(r+r_0)(r+r_1)}}$. □

Theorem 4.

Two circles, C₁ and C₂, are tangent to each other with radii r₁, r₂. Furthermore, these two circles are tangent to a line, as shown in Figure 7. Then,

$$\alpha ={\displaystyle \frac{\pi }{2}}+{\mathit{sin}}^{-1}{\displaystyle \frac{r_2-r_1}{r_2+r_1}}.$$

Proof of Theorem 4.

Assume r₂ > r₁, as shown in Figure 7; then, the angle α is greater than ${\displaystyle \frac{\pi }{2}}$ and α − ${\displaystyle \frac{\pi }{2}}$ = ${\sin }^{-1}{\displaystyle \frac{r_2-r_1}{r_2+r_1}}$. □

Note that if r₂ < r₁, α < ${\displaystyle \frac{\pi }{2}}$, it is because the value of ${\sin }^{-1}{\displaystyle \frac{r_2-r_1}{r_2+r_1}}$ is negative.

In our algorithm for solving the Tri(T_n) problem, we provide a criterion to modify the radius for each circle. Consider the tangency graph for the Tri(T_n) problem. We define three different kinds of circles: corner circles, boundary circles, and inner circles. The corner circle is tangent to two other circles and two sides of the triangle. The boundary circle is tangent to four other circles and one side of the triangle. The inner circle is tangent to the other six circles (see Figure 2 and Figure 3). Here, we illustrate the criterion for the inner circle, boundary circle, and corner circle, respectively.

Assume that n circles C₁, C₂, …, C_n with radii r₁, r₂, …, r_n, are tangent to one circle C and its neighbor circles, and C_n is tangent to C₁, as shown in Figure 8c. In this situation, the circle ring from C₁ to C_n (n = 9 in Figure 8c, is explicitly tangent to the center circle C. Alternatively, circle C is explicitly tangent to circle rings C₁ to C_n. The size of the circle ring is n. When α_i is the angle between two vectors that connect the center of C_i and C and C and C_{i+1 mod n}, we define SA(C) = $\sum _1^n{\alpha }_i$.

Assume that the circle ring C₁, C₂, …, C_n is explicitly tangent to C. If we know the radii for all circles in the circle ring, how do we find the radius r for C? Assume the current radius of C is r, and the circle ring C₁, C₂, …, C_n is explicitly tangent to C without the constraint that C_n is tangent to C₁. We would like to change the value r so that C_n is also tangent to C₁. Assume that n = 9, with a current radius r of C, we can compute SA(C) = $\sum _1^9{\alpha }_i$ using Theorem 3 (see Figure 8). There are three different cases for a SA(C): SA(C) > 2π, SA(C) = 2π, and SA(C) < 2π. If SA(C) = 2π (Figure 8c), we find the radius for C so that the circle rings are explicitly tangent to circle C. If SA(C) < 2π, as shown in Figure 8a, we need to reduce the value r so that the circle ring is explicitly tangent to circle C. On the other hand, if SA(C) > 2π, as shown in Figure 8b, we need to increase the value r so that the circle ring is explicitly tangent to circle C. With this property, the radius of C can be easily found using a binary search algorithm. In fact, from the arc length computation for the circle C, it (2r) × π = (current r) × SA(C) can be derived, and thus we find that r = (current r) × (SA(C)/2π).

In the solution of the Tri(T_n), n > 3 problem, the inner circle is explicitly tangent to the circle ring, and the size of the circle ring is always six (See Figure 9c). Therefore, with an estimated radius r, it is easy to construct an O(1) algorithm to find the radius of C, which satisfies the constraint SA(C) = 2π. This algorithm (See Algorithm 1) has the following steps:

Algorithm 1. The radius for center circle tangents to a circle ring

1: Input the radii for the circle ring r1, r2, …, rn, and an initial radius (r = 1) of C. 2: Using this radius r, compute SA(C). 3: Output the result r × (SA(C)/2π).

Consider the inner circle for the Tri(T_n) problem, as shown in Figure 9c. The angles ${\alpha }_1$, ${\alpha }_2$, ${\alpha }_3$, ${\alpha }_4,{ \alpha }_5,{\alpha }_6$ can be computed using Theorem 3, and the radius of the inner circle can be computed by Algorithm 1.

Now consider the boundary circle (see Figure 9b); the angles ${\alpha }_2$, ${\alpha }_3$, ${\alpha }_4$ can be computed using Theorem 3, and ${\alpha }_1$ and ${\alpha }_5$ can be computed using Theorem 4. When C is a boundary circle, we define SA(C) as the sum of these five angles. Note that we use the same term SA(C) regardless of whether C is an inner circle or boundary circle. Therefore, if C is a corner circle, SA(C) is equal to the sum of the four angles, as shown in Figure 9a. The angle ${\alpha }_1$ is equal to π − ∠A; ${\alpha }_2$ and ${\alpha }_4$ can be computed using Theorem 4, and ${\alpha }_3$ can be computed using Theorem 3. From the above description, we know that SA(C) can be computed regardless of whether C is a corner circle, a boundary circle, or an inner circle.

We know that when the circle radii in the circle ring are fixed, we can find one (inner) circle explicitly tangent to the circle ring. With a similar approach, if the boundary circle with a variable radius is tangent to four circles and one line, we can also find the radius of the boundary circle. Consider the boundary circle in Figure 10; the SA(C) can be computed for the fixed radii of the four circles. When SA(C) < 2π (Figure 10a), we need to reduce the radius of C, and when SA(C) > 2π (Figure 10b), we need to enlarge the radius of C until SA(C) = 2π (Figure 9b). This scenario also works when C is a corner circle (see Figure 11).

We conclude the following: if SA(C) > 2π, enlarge the radius of C, and if SA(C) < 2π, reduce the radius of C. The circle C can be an inner circle, boundary circle, or corner circle.

We describe the criterion used to modify all circles in the Tri(T_n) problem and propose an algorithm in the next section.

4. The Proposed Algorithm to Solve the Tri(T_n) Problem

We present the algorithm and its results in the following section.

4.1. The Algorithm Used to Solve the Tri(Tn) Problem

The proposed algorithm has the following steps.

• Input A, B, and C vertices for triangles and n for Tri(T_n) problem.
• Calculate the initial radii for all T_n circles.
• Use a while loop to modify the radii of all circles until all circles C satisfy SA(C) = 2π within a small tolerance.
• Display the results, including the triangle A, B, and C and all circles.

We implemented the above idea and stepped into an infinite loop. Why did this happen? Essentially, we used angle computation to compute SA(C) for all circles with other circles. If we found one solution for the Tri(T_n) problem for triangle ABC, this solution would also satisfy the constraint for any similar triangles of ABC. Conversely, if we found r_m, where 1 ≤ m ≤ T_n was one solution satisfied for SA(C) = 2π, we multiplied all radii to a constant k, k × r_m, where 1 ≤ m ≤ T_n was also satisfied for SA(C) = 2π. There are infinitely many solutions, so we need more constraints.

Using Tri(T₂) as an example, we attempted to add more constraints. In Tri(T₂), we need to find Malfatti circles using the algorithm we proposed; however, no mathematical solution for this exists. As shown in Figure 12, there are three corner circles that we need to find. With the angle name in Figure 12, α₁ = π − ∠A, α₂ = ${\displaystyle \frac{\mathsf{\pi }}{2}}$ + sin⁻¹${\displaystyle \frac{r_2-r_1}{r_2+r_1}}$, α₃ = cos⁻¹${\displaystyle \frac{{r_1}^2{+r}_1{r}_2{+r}_1{r}_3{{-r}_{2}r}_3}{(r_2+r_1)(r_3+r_1)}}$ and α₄ =${\displaystyle \frac{\mathsf{\pi }}{2}}$ + sin⁻¹${\displaystyle \frac{r_3-r_1}{r_3+r_1}}$. Note that if we enlarge the radii k times (R_i = k × r_i), we find the same values for α₁, α₂, α₃, and α₄. We require one more constraint, such as the length of one side of the triangle (See Figure 12).

Now, the proposed algorithm (See Algorithm 2) is as follows.

Algorithm 2. The Tri(Tn) problem

1: Input the coordinate of three vertices A, B, C, and n; calculate the angle A, B, C, and the edge length c 2: Initial radius list rold = [ri|where 1 ≤ i ≤ Tn]. eps = 0.01. Calculate the new radius list; call it rnew from SA(Ci) = θi using the radii in the old radius list rold. 3: While one of |θi − 2π| > eps: # one of the circle is two large or too small, then 3.1–3.3 3.1: Compute change ratio k from c, the side length of the triangle, and new radius list rnew. 3.2: Modify the radius list at the same time. rold = k × rnew 3.3: Calculate new radius list rnew f from SA(Ci) = θi using the radii in rold. 4: Compute the change ratio k; the solution radii is k × rnew. 5: Display the result.

4.2. Example of the Tri(T_n) Problem

Given the coordinates of A = (0,0), B = (70,0), and C = (−10,20), we obtain the following result (see Figure 13) for the Tri(T_n), n = 2, 3, 4, 8, 30 problem. This lasted 1.69, 1.75, 1.70, 1.76, and 13.15 s, respectively. The radii for Tri(T₂) can be directly computed from a mathematical equation. The number of iterations in the while loop is 62, 100, 338, and 3533 for n = 3, 4, 9, 31, respectively.

5. Implementation Detail and Potential Applications

There are two things that we need to consider when implementing Algorithm 2. The first was how to enlarge/reduce the radius, and the second was how to illustrate all radii once they were found.

To begin with, we set a step value (=0.01), and when the radius r needed to be enlarged, we added the value r = r + step, similarly reducing the radius (r = r − step). This approach made the algorithm very inefficient. For example, it took 20,391 iterations (3 s) to solve the Tri(T₃) problem, and thus, we required a more effective method of enlarging/reducing the radius. This enlarge/reduce strategy had to correspond to the surrounding angle of the circle. The new radius had to have a circumference equal to the circular arc length, whose radius was r and angle was $\theta$, i.e., ${\mathrm{r}}^{\prime }={\displaystyle \frac{\theta }{2\pi }}\mathrm{r}$. Note that when $\theta$> $2\pi$, we enlarged the radius (r′ > r), and when $\theta$< $2\pi$, we reduced the radius (r′ < r). Using this approach to enlarge/reduce the radii, the same example took 62 iterations (less than 2 s).

The main task for the drawing process was to find the center of each circle. Consider three cases as follows (See Figure 2):

• The center of C_1,1: This circle is a corner circle, and we want to determine the center of C_1,1 from two edges and a radius value (r_1,1) for the corner circle.
• The center of C_2,1: This circle is an edge circle when n > 1. From the above step, we can determine the center and radius of C_1,1. With the one side of the triangle $\overline{AC}$, we can find the center of C_2,1. With this approach, we can find the center of C_i,1 for all circle circles 1 < I < n.
• The center of C_2,2: If we determine the center and radii of C_1,1, C_2,1, from the above two steps and from the radius of C_2,2, we can find the center of C_2,2.

The above three problems can easily be solved using simple geometry. Furthermore, if we solve the center position for circles row-by-row (from left to right in Figure 2), it falls in one of the above three questions so that every center of the circles can be easily found. After we find the center of all circles with their associated radii, the drawing process becomes simple.

This problem can be applied to several different applications, such as the following:

• Logo design: the design of logos for different products.
• Product design: for a triangle prism comprising six bottles of different sizes and radii containing different liquids, the radii can be calculated.
• Radar location design: In a triangle area, a radar system can be established consisting of several radars, with each radar having a different radius working in a circular area. This working circular area is much smaller than the area of the triangle. Our algorithm can determine the center of each radar, and the radii of the circular area should be greater than the radii we find from the algorithm so that every object that passes this triangle area will be detected by one of the radars, i.e., nothing can pass this triangle area.
• Wireless transmitter location design: Similar to radar location design, the application of the algorithm can determine the center of a wireless transmitter location and what kind of wireless transmitter we should use. Larger radii are used so that the union of the circular area covers the triangle, and any location inside the area can receive wireless signals.
• Mouse pad design: Suppose that there is a triangle pad, and we want to cut this pad into different sizes of circular mouse pads. The algorithm proposed in this paper can suggest a method for cutting the pad. Notice that a different initial value r can produce a different number of circular pads.

6. Conclusions and Future Research

The Tri(T_n) problem can be solved by the proposed O(T_n) algorithm. This algorithm can solve the Tri(T₄₆) (1128 circles) problem in less than one minute without a display.

We know that the Tri(T₁) and Tri(T₂) problems have unique solutions. One solution can be found using the algorithm we proposed, but it is unclear whether the solution is unique for Tri(T_n), n > 2. Therefore, the uniqueness property or its counter-example for the Tri(T_n) problem is a topic for future research.