Packing Circles

21

1

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

enter image description here

(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:

enter image description here

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.

enter image description here

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

El'endia Starman

Posted 2015-11-22T19:35:44.090

Reputation: 14 504

3Waiting on Hexagony, I'm betting. ;D – Addison Crump – 2015-11-22T22:12:55.407

@VoteToClose: I don't think Hexagony has graphical output, but MAN, that'd be awesome! – El'endia Starman – 2015-11-22T23:09:40.083

@El'endiaStarman Well, you could write an SVG to stdout, but I don't think I'm going to... :P – Martin Ender – 2015-11-23T09:57:00.847

1Wow, no-one has thanked me in bold for my comments in the sandbox before. I'm blushing :-D Of course I commented because I liked the challenge, though I'm not sure if i'm going to have time to answer it. – Level River St – 2015-11-23T20:19:07.723

Per my discussion with Reto Koradi on user81655's answer, I think the largest hexagon we will see with sharp corners is sidelength 7d (8 circles.) That's N=169 circles total. You could consider restricting the problem to that number, which would give more chance of getting a correct answer (currently there aren't any) and of being able to check. On the other hand it may be more interesting to leave the problem open up to arbitrary N. – Level River St – 2015-11-24T08:34:11.410

@steveverrill: I think I'll go with the "interesting" choice and require that it work for arbitrary N (within reason, of course). – El'endia Starman – 2015-11-24T08:36:51.330

Update: there is a better solution for N=169 than a perfect hexagon. We leave 2 opposite corners alone, and remove the circles from the remaining 4 corners. We place them on the sides of 5d (6 circles) thus created as near to the middle of the side as possible (as there is an odd number of gaps, there are 2 distinct ways of doing this for each side.) The resulting figure has a perimeter of 41.933 instead of 42. Is it the best possible? probably, I don't know. – Level River St – 2015-11-24T09:22:40.520

This is looking more and more like a code-challenge rather than a code-golf problem! – DavidC – 2015-11-24T16:07:36.560

@DavidCarraher: Haha, yeah, I wasn't totally sure which one to pick before I posted. I don't know if it would be acceptable to change the problem type now, almost 48 hours after it was posted. – El'endia Starman – 2015-11-24T19:01:57.687

I would change it to code-challenge, even at this point, because that will encourage people to pay attention to less than perfect but interesting proposals. It may also encourage people to invest in more imaginative approaches. – DavidC – 2015-11-24T21:17:26.603

@DavidCarraher: I do like that idea. But what should the scoring criteria be? I'm thinking "the first answer to get the best solution for n=1000". – El'endia Starman – 2015-11-25T00:57:09.493

Strangely enough, the solution for n =1000, or any large number, should be relatively easy: you simply (I think) shrink a circle, with center on 1 hex grid point until the circle holds 1000 hex grid points. You still may have to make minor adjustments because the most efficient solution may lie on a diagonal between two neighboring points. – DavidC – 2015-11-25T01:01:44.920

Maybe a popularity contest? You might want to raise the issue of the proper tag in the sandbox. – DavidC – 2015-11-25T01:03:27.680

@DavidCarraher: The Sandbox seems like a strange place to bring that up. The corresponding post has already been edited and deleted. But bringing it up in a separate Meta question also seems a bit strange. Chat would probably be best, but there are few people around (likely because of the upcoming Thanksgiving break). – El'endia Starman – 2015-11-25T01:06:40.390

Answers

4

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.

disks


DavidC

Posted 2015-11-22T19:35:44.090

Reputation: 24 524

1As I mentioned on user 81655's answer, the protruding single circle on 22 (and 17, 25, 28, 31, 34) would be better placed at the middle of the row of circles on which it sits. – Level River St – 2015-11-23T23:01:10.103

I thought so also, but then I noted that 9, which also has a protruding circle was considered correct. When I have some time, I'll compare the measurements of the convex hulls (of the centers). – DavidC – 2015-11-24T01:05:21.727

in 9 the protruding circle is either 1/4 or 3/4 along the flat row, so it makes no difference. in 17, 22, 25, 28, 31 the protruding circle is 1/6, 3/6 or 5/6 along, so the middle position is better (think about pulling a string sideways: it's easier to pull from the middle because that way the string has less extension to do. In 34 (and 35) we have 1/8, 3/8, 5/8 and 7/8 along the flat side. So for these we should choose 3/8 and 5/8 before 1/8 and 7/8. – Level River St – 2015-11-24T01:19:40.777

You're absolutely right and this is confirmed by measurements. – DavidC – 2015-11-24T02:07:52.257

This is awesome! The transition 30->31 shows that we can't just take the previous shape and add a circle to the outside (that would have given a perimeter of 16.464.) There's also at least one case where you could have just added one circle to the outside, but chose a different arrangement: 12->13 – Level River St – 2015-11-24T20:23:30.533

Nice observations. I am especially puzzled by 30 because I thought my routine would build at most 1 layer around a complete regular hexagon. – DavidC – 2015-11-24T21:06:32.770

It did only build one layer. In 27=19+8 it put the additional 8 at the bottom, but in 30=19+11 it put them top, bottom and right (or if you prefer, top, bottom and left.) If you did them different colours you would see that the additions are different. Yet, by coincidence, the shape of 27 is fully contained in 30. – Level River St – 2015-11-24T21:58:23.723

You are right about 30 circles. I used your suggestion to color the "additional" circles in red. It really helps parse the figures. – DavidC – 2015-11-25T00:54:38.007