Circle positioning algorithm
The Sugar mesh view consists of a number of icons, many of which are circular in nature. We would prefer that these icons not overlap each other, so that the user may easily see all of them. However, we would also like these icons to stay near some fixed position, so that when glancing from one screen to another, or at the same screen over time, one may quickly find a particular icon of interest.
Mathematically, then, the problem is as follows. We have a number of circles, labeled by <math>i\in[1\dots N]</math>. Each of these circles has a radius <math>r_i</math> and an ideal location <math>\left< a_i, b_i\right></math>. However, each circle has been moved to a new location <math>\left< c_i, d_i\right></math>. Our goal is to choose these locations to minimize <math>\sum_i (a_i-c_i)^2 + (b_i-d_i)^2</math>, subject to the constraint that for each pair of circles <math>i</math> and <math>j</math>, <math>\sqrt{(c_i-c_j)^2 + (d_i-d_j)^2} \geq r_i + r_j</math>.
Our cost function above is obviously quadratic in nature. If we square both sides of the constraint to yield the equivalent constraint <math>(c_i-c_j)^2 + (d_i-d_j)^2 \geq (r_i + r_j^2</math>, we see that the constraint is quadratic as well. This problem is therefore a Quadratically constrained quadratic program.
Unfortunately, as that page notes, the generic QCQP problem is NP-hard. In particular, QCQP can be NP-hard when quadratic constraints are nonconvex. Unfortunately, the constraints in this case are indeed nonconvex, and so it is possible (though not certain) that this circle-packing problem is intractably hard.
One way to avoid the difficulty of solving a nonconvex optimization problem is to choose a convex subspace. This subspace excludes many valid solutions, but it reduces the problem to a convex optimization, which can typically be solved by a fast algorithm. In our case, replacing the quadratic contraints with a linearization turns the QCQP problem into a classic linearly constrained quadratic programming problem, for which there are many solver libraries available, such as CVXOPT.
