# An open problem in greedy geometric algorithms

I've been working on improving the Wikipedia article on the Malfatti circles, three mutually-tangent circles packed into a triangle. While doing so, I ran across an interesting open problem on greedy algorithms for geometric optimization.

The Malfatti circles had been studied by others earlier, but in 1803 Gian Francesco Malfatti used them to solve (he mistakenly thought) the case *n* = 3 of the following optimization problem:

**Input:** A triangle *T* and a number *n*.**Output:** A set of *n* circles inside *T*, with disjoint interiors, having the maximum possible total area.

Through the work of Lob and Richmond (1930), Goldberg (1967), and Zalgaller and Los' (1994), it was shown that, actually, Malfatti's solution is never optimal. Instead, the problem is solved optimally by a simple greedy procedure that repeatedly selects the largest circle in *T* that is disjoint from all previously-selected circles.

Mellisen (1997) conjectured that the same greedy algorithm finds the *n* area-maximizing circles for any *T* and *n*. At each step of the algorithm, the remaining uncovered pieces of the input triangle are themselves triangular in shape, bounded by three straight or curved sides; this invariant not only simplifies the algorithm, it also makes it plausible that some sort of inductive proof of the conjecture might be possible. But as of the recent survey by Andreatta, Bezdek and Boroński (2010) it seems to remain unsolved.