With f a fixed transient function, the only remaining problem is the minimization problem: show that the corrected volume F(p) = \vol(V(p)) + f(p), for p Î C, is at least the volume v_\fcc of the rhombic dodecahedron. The space of clusters C is so complicated that we cannot minimize F directly. We associate with each cluster p Î C a planar graph that identifies the most prominent geometrical features of the cluster. Next, we give a lower bound on the value of F(p) that depends only on the combinatorial structure of this planar graph. In most cases the combinatorial lower bound on F(p) is greater than v_\fcc as desired. The combinatorial approximation to F(p) is rather crude, and sometimes it fails to give the lower bound we want. By means of a computer search, we can generate all planar graphs for which the combinatorial lower bound on F(p) is less than v_\fcc. If F(p) < v_\fcc, the planar graph of p must appear on this computer-generated list of possibilities. This list contains about 5000 planar graphs.

The planar graph of a cluster p is easy to construct. Each edge of the graph corresponds to pairs of balls that are close to the ball at the origin and that are close to each other. Set t = 4Ö[(3/7)] » 2.618. Closeness is determined by a parameter T Î (2,t) (we use T = 2.51, but this is rather arbitrary). If two ball centers have distance at most T from the origin, and distance at most T from each other, we draw a circular arc on the unit ball at the origin connecting the two unit direction vectors pointing to the two ball centers (Figure \X6). %\footnote"*"{N.B. %Insert a figure showing the intersection of a sphere and a triangle.}

These circular arcs do not meet, except at their endpoints. In fact, this is why we require that T < t. If T = t, we have the configuration of ball centers shown in Figure \X7. %\footnote"*"{N.B. Insert %a figure showing an equilateral triangle with edges of length }$\tau$\special{html:, and %a segment of the same length in the normal direction passing through the %center.} The edges all have length 2 or t, and the edges of length t are marked with heavy lines. The edges A and B give crossing arcs on the sphere at the origin 0. For any smaller T, the arcs cannot cross.

The planar graph - or more accurately, the spherical graph - associated with a cluster p is the one formed by this system of arcs on the unit sphere. For example, the planar graph associated with the face-centered cubic packing is an alternating pattern of equilateral triangles and squares, with two triangles and two squares meeting at every vertex. The planar graph associated with the regular dodecahedral cluster is the icosahedral graph with 20 triangles arranged five to a vertex.

In the complement of this collection of arcs on the unit sphere, we call the closure of each connected component a standard region. In simple cases, these standard regions are just spherical polygons on the unit sphere. But in general, they may be much more complicated. The most difficult estimates in the proof of the Kepler conjecture are those that establish that the complicated standard regions are never optimal. This is done by making a combinatorial approximation to the minimization problem. We calculate a lower bound on F(p) that depends only on the combinatorial structure of the planar graph associated with p.

Most of my time between 1995 and 1998 was spent working out a proof of these combinatorial lower bounds. Already in 1994, I knew what the bounds should be, but the proofs eluded me. The primary difficulty was with standard regions with a large number of sides. As the number of sides increased, the dimension became too large for me to handle.

The eventual proof was shaped by the capabilities of computers. If computers had been more powerful, the proof might be drastically shorter. If computers had been less powerful, I would still be working toward a solution. As a result of the development of computers, the proof of the Kepler conjecture 50 years from now will be entirely different from what it is today.

A simple heuristic told me what I could get from a computer. My computer was generally able to prove statements about a single tetrahedron, but failed to prove anything about more complicated geometrical objects. In other words, my computer could tell me about the six-dimensional space parametrizing the edge lengths of a tetrahedron but was too slow to handle seven dimensions. Given that the Kepler conjecture is an optimization problem in about 70 variables, this limitation was a frustrating one. The challenge of the problem was to come to a thoroughly six-dimensional understanding of a 70-dimensional space.