A easy visualization is scattering numerous pennies onto a tabletop. If all pennies lie flat on the table (none on top of another), that is a packing. If the pennies are arranged so that no additional pennies may be laid on the table (without overlapping part of an existing penny), the packing is saturated.
Next, the idea of a Voronoi Cell needs to be defined. Given a set of points P = {p0, p1, p2, ...} in a plane, one can partition the plane into Voronoi Cells (polygons) such that a Voronoi Cell about a point p in P consists of all points in the plane which are closer to p than any other point in P. The edges of a polygonal Voronoi Cell represent all points equidistant of two points in P, and vertices where three or more edges meet indicate a point which is equidistant of three (or more points) in P. An edge (say between p0 and p1) of a Voronoi Cell is clearly a line segment which is a subset of the perpendicular bisector of the line segment connecting p0 and p1.
The problem may have its focus narrowed to simply seeing how many circles one can 'squeeze' around a central circle to force that central circle to have a many-sided Voronoi Cell. What occurs outside of this 'ring' of circles is more or less inconsequential... it is easy enough insure that the packing is saturated outside of the ring. The trickiness of constructing this ring of circles about a central circle is that one must find a compromise between packing as many circles as possible while making sure that each circle, in fact, contributes an edge to the resulting Voronoi Cell about the central circle. The danger is that a particular circle's neighbors may 'cut off' it's contribution if these neighbors are positioned too closely (for example) to the central circle. And, of course, one cannot use an arbitrarily large number of circles in the ring since geometrically the resulting ring might leave too much space vacant, violating the saturated condition.
So, the problem can be attacked from two directions: providing examples of valid constructions that increase the lower bound on the number of possible sides, and decreasing the upper bound by proving that too many circles will necessarily 'unsaturate' the packing, or will at least not help by contributing additional sides to the central Voronoi Cell.
Trying to place 12 circles equally about the central circle (to form a regular dodecagon Voronoi Cell) yields an invalid arrangement. The illustration proving its unsaturated state is quite pretty (see Figure); it was shown to me during the MH639 class by W. Kuperberg.
The question then comes up, however, as to whether one could shift the 12 circles slightly so as to keep 12 sides to the central Voronoi Cell (though not regular -- regularity is not a necessary condition), but blocking the vacant space available in the regular dodecagon example. The fit of the interior circles in the illustration is exact. There is no extra room, so one might think that it is possible to alter the configuration oh-so slightly.
After (way too) many rearrangements (and many distance/line calculations) no increase of the lower bound was made, so I then decided to leave the lower bound at 11 and start approaching the problem from the top... and go down on the upper bound.
LEMMA 1. Let p1 & p2 be points in a standard Cartesian Plane. Let l1 and l2 be the line segments joining p1 with the origin (p0) and p2 with the p0, respectively. Let m1 and m2 be the perpendicular bisectors of l1 and l2, respectively. Let angle A be the angle formed by l1 and l2. Under the following conditions:
the measure of A > 30°.
Proof: From condition 5, we get:
The equations of m1 and m2 are:
And so:
From this we get:
4 > (b/2)2 + ((c2+ d2 - bd)/2c)2 = b2c2/4c2 + (c4 + c2d2 - 2c2bd + d4 + c2d2 - 2bd3 + b2d2)/4c2 = (c2(c2 + d2 - 2bd + b2) + d2(c2 + d2 - 2bd + b2))/4c2 = (c2 + d2)(c2 + d2 - 2bd + b2)/4c2 (by i. we get next) >= (c2 + d2)(4)/4c2 = (c2 + d2)/c2 = 1 + (d/c)2 implying -3½ < d/c < 3½
but d/c is simply the slope of line segment l2 and since arctan(3½) = 60°, the angle formed by line segment l2 and the positive x-axis must be strictly less that sixty degrees, this implies that the angle A must be strictly greater than 30°.
The area of the circle of radius 5 centered at the center of c0 is 25*PI. The area of a unit circle is PI. Thus, one can crudely estimate that no more than 25 circles can be packed into the circle of radius 5... meaning that at most 24 sides could appear on the Voronoi cell about one of the circles (25 circles, but a 'central' circle will not add another side to its own Voronoi Cell by itself).
This is a very rough bound, but it is a start.
Proof: Let c0 be a 'central circle' around which circles (c1, c2, ..., cn) each contribute a side to the Voronoi Cell about c0. Assume n is the maximum integer such that each circle so contributes. Consider two circles of the ring (say, cj and ck) such that cj and ck are 'immediate neighbors in the ring' in the sense that if one forms a line segment for each ring-circle by connecting its center with the central circle's center (labeled l1, l2,... ln), there exists no integer i such that li divides the angle formed by lj and lk.
One may orient a Cartesian Plane coordinate system such that the center of c0 is the origin, the center of cj lies on the positive y-axis, and the center of ck lies in Quadrant I (the center of ck cannot be on the positive y-axis (no room); if ck's center is in Quadrant II, reflect by symmetry without loss of generality; if the center of ck lies below the x-axis, it is clear that n is not maximal).
By the construction methods of Voronoi Cells, and the fact that the packing of the plane is saturated, all of the conditions of Lemma 1 are met.
This implies n must be (strictly) less than 12 since the angle between any two line segments lj and lk must be greater that 30°
Suppose S is a satured packing of 3-space by unit spheres, and V is the partitioning of space into Voronoi Cells (polyhedra) about the centers of the spheres. What is the maximum number of faces that any of the Voronoi Cells of V can have?
Often when one extrapolates from 2 to 3-space analogous problems get messier. This is no exception. The best that I have been able to get on this problem is a range of possible solutions based on a lower bound and upper bound. The two bounds are 'close' to one another, but not equal yet. Let's start at the bottom end first.
Finally, it is necessary to show that the 'shell' of spheres saturates the area about the central sphere in the sense that an additional sphere may not be placed within the shell. This can be done fairly easily (calculations will be provided soon).
Thus, a lower bound of 44 is obtained for the problem.
Proof: Let s0 be a 'central sphere' about which n spheres (s1, s2, ..., sn) are situated such that each contributes a face to the Voronoi Cell about s0 and n is the maximum integer for which those conditions hold. Let l1, l2, ... ln be the line segments connecting the center of s0 with s1, s2, ..., sn (respectively), and q1, q2, ... qn be the planes which are perpendicular to, and pass througn the midpoint of, l1, l2, ..., ln repsectively. Orient a Cartesian coordinate system such that s0 is centered at (0,0,0), si (1 <= i <= n) is at (0,y,0) with y > 0, and let sj be the 'nearest' sphere to si ('nearest' meaning that the angle formed by li and lj is not larger than the angle formed by li and any other line segment lk (1 <= k <= n)).
Since sj is nearest to si, qj and qi necessarily form an edge, e, of the Voronoi Cell about s0. Furthermore, e must be an actual line segment (not just a point). Any point on e must lie within distance 2 of (0,0,0); as must the point, p, on the line containing (extending) e which is closest (and equidistant) from the centers of s0, si, sj (note a proof that p is actually on e is not given -- nor is it necessary).
Consider the plane which contains the centers of s0, si, sj. This will necessarily contain li, lj, and p. Furthermore, these centers of s0, si, sj, and the point p satisfy the conditions of Lemma 1 (note that the center of sj must lie in Quadrant I (or at least QII -- symmetric) in order for n to be maximal). This shows that the lines l1, l2, .. ln must all be at least 30° apart from one another.
Now imagine if those line segments were extended radially away from the origin so that they intersected a sphere of radius 4 about the origin. The measures of the angles between the lines would not change. Furthermore, each of those intersection points (call them t1, t2, ... tn) must form the center of a 'cap' which is a section of the radius 4 sphere. If the diameters of the caps are formed by considering a 30° angle-width from the origin (15° on either side of the center of the cap, see figure)... then none of the caps will overlap one another.
By surface of revolutions in Calculus, one can detemine the surface area of such a cap to be: 8*PI*x where x is the 'height of the cap' (the distance from it's t-center to the plane containing the cap's circular edge).
Basic trigonometry shows that x =~ 0.13629...
Now, the surface area of the radius 4 sphere is 64*PI, so no more than:
(64*PI)/(8*PI*x) caps can reside on the surface an still be mutually disjoint.
The solved value is ~58.69... or at most 58 caps.
If these two beliefs are true, that would allow us to lower the upper bound of the problem to:
(64*PI*PI*3½)/(8*PI*x*6) ... where x =~ 0.13629...
this yields: ~53.229... or at most 53 spheres (i.e.: sides to the polyhedral Voronoi Cell) about s0.
If this limit on density could be improved by considering not a general cap-on-surface approach but with the specific case of a 15° angle-radius... maybe upper bound could be lowered further. I (intuitively) see little improvement on the lower end (maybe up to 45 or 46).