Packing Circles

Question

Take a look at this image. Specifically, at how the holes on the ends are arranged.

^{(Image source)}

Notice how the pipes in this image are packed in a hexagonal pattern. It is known that in 2D, a hexagonal lattice is the densest packing of circles. In this challenge, we will be focusing on minimizing the perimeter of a packing of circles. One useful way to visualize the perimeter is to imagine putting a rubber band around the collection of circles.

The Task

Given a positive integer n as input, show a collection of n circles packed as tightly as possible.

Rules and Clarifications

• Assume circles have a diameter of 1 unit.
• The variable to be minimized is the length of the perimeter, which is defined to be the convex hull of the centers of the circles in the group. Take a look at this image:

The three circles in a straight line have a perimeter of 4 (the convex hull is a 2x0 rectangle, and the 2 is counted twice), those arranged in a 120-degree angle have a perimeter of about 3.85, and the triangle has a perimeter of only 3 units. Note that I am ignoring the additional pi units that the actual perimeter would be because I'm only looking at the circles' centers, not their edges.

• There may (and almost certainly will be) multiple solutions for any given n. You may output any of these at your discretion. Orientation does not matter.
• The circles must be on a hexagonal lattice.
• The circles must be at least 10 pixels in diameter, and may be filled or not.
• You may write either a program or a function.
• Input may be taken through STDIN, as a function argument, or closest equivalent.
• The output may be displayed or output to a file.

Examples

Below I have example valid and invalid outputs for n from 1 to 10 (valid examples only for the first five). The valid examples are on the left; every example on the right has a greater perimeter than the corresponding valid example.

Much thanks to steveverrill for help with writing this challenge. Happy packing!

Answer 1

Mathematica 295 950 bytes

Note: This still-to-be-golfed version addresses issues raised by Steve Merrill regarding my earlier attempts.

Although it is an improvement over the first version, it will not find the densest handle configuration where one would seek a circular, rather than hexagonal, overall shape.

It finds solutions by building a complete inner hexagon (for n>=6, and then examines all of the configurations for completing the outer shell with the remaining circles.

Interestingly, as Steve Merrill noted in the comments, the solution for n+1 circles does not always consist of the solution for n circles with another circle added on. Compare the given solution for 30 circles to the given solution for 31 circles. (Note: there is a unique solution for 30 circles.)

m[pts_]:={Show[ConvexHullMesh[pts],Graphics[{Point/@pts,Circle[#,1/2]&/@ pts}], 
ImageSize->Tiny,PlotLabel->qRow[{Length[pts],"  circles"}]],
RegionMeasure[RegionBoundary[ConvexHullMesh[pts]]]};
nPoints = ((#+1)^3-#^3)&;pointsAtLevelJ[0] = {{0,0}};
pointsAtLevelJ[j_]:=RotateLeft@DeleteDuplicates@Flatten[Subdivide[#1, #2, j] &@@@
Partition[Append[(w=Table[j{Cos[k Pi/3],Sin[k Pi/3]},{k,0,5}]), 
w[[1]]], 2, 1], 1];nPointsAtLevelJ[j_] := Length[pointsAtLevelJ[j]]
getNPoints[n_] := Module[{level = 0, pts = {}},While[nPoints[level]<=n, 
pts=Join[pointsAtLevelJ[level],pts];level++];Join[Take[pointsAtLevelJ[level],n-Length[pts]],
pts]];ns={1,7,19,37,61,91};getLevel[n_]:=Position[Union@Append[ns,n],n][[1, 1]]-1;
getBaseN[n_] := ns[[getLevel[n]]];pack[1]=Graphics[{Point[{0,0}], Circle[{0, 0}, 1/2]}, 
ImageSize->Tiny];pack[n_]:=Quiet@Module[{base = getNPoints[getBaseN[n]], 
outerRing = pointsAtLevelJ[getLevel[n]], ss},ss=Subsets[outerRing,{n-getBaseN[n]}];
SortBy[m[Join[base,#]]&/@ss,Last][[1]]]

Some of the checks entailed comparisons of over one hundred thousand cases for a single value of n (including symmetries). It took approximately 5 minutes to run the total 34 test cases. Needless to say, with larger n's this brute-force approach would soon prove impractical. More efficient approaches are certain to exist.

The numbers to the right of each packing are the perimeters of the respective blue convex hulls. Below is the output for 3 < n < 35. The red circles are those added around a regular hexagon.

---