The Algorithm to Solve the Extend General Malfatti’s Problem in a Convex Circular Triangle

Authors: Ching-Shoei Chiang

Abstract:

The Malfatti’s problem solves the problem of fitting three circles into a right triangle such that these three circles are tangent to each other, and each circle is also tangent to a pair of the triangle’s sides. This problem has been extended to any triangle (called general Malfatti’s problem). Furthermore, the problem has been extended to have 1 + 2 + … + n circles inside the triangle with special tangency properties among circles and triangle sides; it is called the extended general Malfatti’s problem. In the extended general Malfatti’s problem, call it Tri(Tn), where Tn is the triangle number, there are closed-form solutions for the Tri(T₁) (inscribed circle) problem and Tri(T₂) (3 Malfatti’s circles) problem. These problems become more complex when n is greater than 2. In solving the Tri(Tn) problem, n > 2, algorithms have been proposed to solve these problems numerically. With a similar idea, this paper proposed an algorithm to find the radii of circles with the same tangency properties. Instead of the boundary of the triangle being a straight line, we use a convex circular arc as the boundary and try to find Tn circles inside this convex circular triangle with the same tangency properties among circles and boundary as in Tri(Tn) problems. We call these problems the Carc(Tn) problems. The algorithm is a mO(Tn) algorithm, where m is the number of iterations in the loop. It takes less than 1000 iterations and less than 1 second for the Carc(T16) problem, which finds 136 circles inside a convex circular triangle with specified tangency properties. This algorithm gives a solution for circle packing problem inside convex circular triangle with arbitrarily-sized circles. Many applications concerning circle packing may come from the result of the algorithm, such as logo design, architecture design, etc.

Keywords: Circle packing, computer-aided geometric design, geometric constraint solver, Malfatti’s problem.

References:

[1] Fukagawa, H. and Pedoe, D. "The Malfatti Problem." Japanese Temple Geometry Problems (San Gaku). Winnipeg: The Charles Babbage Research Centre, pp. 28 and 103-106, 1989.
[2] O. Bottema, “The Malfatti Problem,” Forum Geometricorum 1, 43-50, 2000.
[3] M. Stefanović. “Triangel centers associated with the Malfatti circles.” Forum Geometricorum 3,83-93, 2003.
[4] Wolfram MathWorld. “Malfatti Circles,” http://mathworld.wolfram.com/MalfattiCircles.html
[5] Ching-Shoei Chiang, Christoph M. Hoffmann, Paul Rosen, “A gereralized Malfatti’s Problem”, Computational Geometry, Volume 45, Issue 8, October 2012, pages 425-435.
[6] Ching-Shoei Chiang, Hung Chieh Li, Min-Hsuan Hsiung, and Fan-Ming Chiu, “Extended General Malfatti’s Problem, The 19th International Conference on Scientific Computing, 2021/7/26-29.