In some cases, the crude combinatorial bounds were not good enough. One case turned out to be far more intricate than the others, and it became the subject of Ferguson's thesis. The remaining 4999 or so planar graphs were analyzed individually. For each, there is a large-scale nonlinear optimization problem to be solved. Minimize F(p) subject to the constraint that the cluster be associated with the given planar graph. Nonlinear optimization problems of this size can be hopelessly difficult to solve rigorously. We might easily have come this close to a solution only to be thwarted in our attempts by nonlinearities. But a new observation carries us forward: the large-scale structure of the problem is linear and can be solved by linear programming methods.
The large-scale linearities of the problem can best be understood by turning back to the problem, solved by McLaughlin, of minimizing the volume of a truncated Voronoi cell. Here there is no correction term, $f=0$, and to further simplify, let assume that there is no truncation so that the full Voronoi cell lies inside a ball of radius $\sqrt{2}$ at the origin. We divide the Voronoi cell into simplices according to any convenient scheme. To fix our attention, here is one possibility. Drop a perpendicular from each face (at point on the face we will call $v$) to the center of the Voronoi cell. Drop a perpendicular from each edge (at a point $w$) of the face to $v$. The vertices of a simplex are the center of the Voronoi cell, the point $v$ on the face, the point $w$ on the edge of the face, and finally either endpoint of the edge. These simplices partition the Voronoi cell.
Instead of minimizing the volume of the Voronoi cell directly we can introduce variables $x_i$ representing the volumes of the individual simplices. We minimize the sum of the $x_i$ (which is certainly linear in $x_i$), subject to the constraint that the pieces fit together. The assembly constraints are all linear. There are constraints of the form $z=z'$ (which is linear in $z$ and $z'$), where $z$ is the length of an edge of a simplex, and $z'$ is the length of a matching edge of a second simplex that shares an edge with the first. There are constraints of the form $\alpha_1+\alpha_2+\cdots+\alpha_k=2\pi$ (linear in $\alpha_i$) that stipulate that the dihedral angles of the simplices around an internal edge should sum to $2\pi$, and there are similar linear constraints for edges that lie on a face of the Voronoi cell. The problem becomes a massive linear programming problem.
There is a flaw in this argument - there are unavoidable nonlinear constraints. The volumes $x_i$ and the dihedral angles $\alpha_i$ are nonlinear functions of the edge lengths of a simplex. Nevertheless, the large-scale structure of the problem is linear. The nonlinear relations are the relations that hold for a simplex in isolation. These nonlinearities involve a small number of variables and can be treated by computer according to the heuristic principle enunciated above that the computer can tell us whatever we want to know about a single simplex. In particular, the computer verifies inequalities between volumes, dihedral angles, and edge lengths that can be used as linear substitutes for the nonlinear relations.
If we now go back to the Kepler conjecture, so that the correction term $f$ is nonzero, the large-scale structure of the problem is still linear. In fact, the function $f$ is defined geometrically as a linear combination of volumes. Knowing that linear programs would be an essential part of the proof, I was careful to choose a function $f$ adapted to that end. By breaking larger objects into smaller objects, we can express the minimization problem in terms of simple quantities such as areas of spherical triangles and volumes of simplices, subject to linear assembly constraints. All nonlinearities of the problem are confined to a small number of variables.