My bundle of 19 fullerenes is arranged in a face-centred cubic lattice, each ball occupying one of the 24 even-numbered cells of a 4×4×3 array (and parts of the adjacent cells). The spacing of the grid planes is determined by the sums of the radii of the circumspheres of nearest-neighbor balls.
There appears to be much more ‘daylight’ between balls than necessary. That’s not a problem here, as the size of the bounding box is not near the limits of the process; but still it got me thinking about how to tighten the packing.
The first step is to stop thinking of the objects as rough spheres. Each one’s assigned space in the lattice is a rhombic dodecahedron (hereinafter “RD”): a cuboid augmented by six pyramids. So, for each object, find its minimal bounding RD: the planes that meet its extreme points in 12 directions (±x±y, ±x±z, ±y±z). These planes define two kinds of vertex: the eight of a rough cuboid and twelve of a rough octahedron. (A regular octahedron has six vertices, of course, but in general the planes won’t coincide in fours and so each such vertex splits into two.) The cuboid vertices determine the grid spacing.
It’s likely that the tangent RD can be shrunk by rotating the object within it. Treating the object as a convex polyhedron, I’d pick the three vertices nearest to each plane and find what rotation would make their own plane parallel to the bounding plane; apply the sum of the resulting 12 torque vectors; repeat until convergence. (You’d probably want to try this process many times from random starting orientations, to avoid bad local minima.)
The next question is how to assign the objects to their cells, given that their sizes differ (and some may be zero). My intuition says to turn each RD so that Δx ≤ Δy ≤ Δz, say, and try to minimize, within each plane, the variation of the dimension orthogonal to that plane; big should alternate with small, and the fattest planes should be interior to minimize extensions outside the overall box.
After all that, the RDs can shift out of their crystalline positions to reduce leftover space around them.
Of course, all of this goes out the window if the objects naturally fill some other tiling shape.
I might try annealing.
So here’s my current idea (which I don’t expect to try). The number to be minimized is the maximum dimension of the bounding box. Annealing steps consist alternately of rotating an object and swapping two objects (one of which may be empty); after each such step, coordinates for the objects’ centers are found by the simplex method; I hope there’s a black-box simplex function that can minimize the maximum of a set of linear functions.