Can You Pack the Circles?

This Week's Fiddler

With square packing, the rectangular area that fits a unit circle would be 2 wide and 2 high, meaning 4 square units. Our calculation here is rather simple because these rectangular areas perfectly tesselate to form the larger rectangle, given no gaps on the edges. Thus, because 8 wide is perfectly divisible by 2 wide, and because the vertical height is guaranteed to have no gaps, there will always be $\frac{1}{4}$ packing efficiency (number of unit circles per unit of square area).

With hexagonal packing, things are a bit trickier, especially because the number of circles that fits in each row alternates between 4 and 3, for odd and even rows (counting from 1), respectively.

1 row of hexagonally packed circles will still be 2 high. However, adding a new row does not add a complete 2 to the height because some of the second row's height overlaps with the first row's. To find how much height adding a new row contributes, we can find the distance between the center of a circle on one of the rows with the center of a circle in a row directly above.

Imagine three circles stacked in an equilateral triangle formation, similar to the 𑗘 character, where line segments can be drawn between the centers of each circle. The segments drawn between rows form $\frac{\pi}{3}$ radian angles with the horizontal and have a length of 2 unit radii, or 2. This means the segment's height within each circle is $2\sin(\frac{\pi}{3})=2\cdot\frac{\sqrt3}{2}=\sqrt3$. Thus, each row added to the hexagonal packing adds $\sqrt3$ to the height.

Hence, for $r$ rows of hexagonally packed unit circles within a rectangle of width 8, the height $h$ is defined as $h(r)=2+\sqrt3(r-1)$. In our case with four rows, this makes $h(4)=2+\sqrt3(4-1)=2+3\sqrt3\approx7.1962$ length units. The area is 8 times that, or $16+24\sqrt3\approx57.5692$ square area units.

How about the number of circles? For this part, it's just 14, making our packing efficiency $\frac{14}{16+24\sqrt3}\approx0.2432$ circles per unit of square area.

Therefore, square packing, at 0.25 circles per unit of square area, is more efficient.

Answer: square packing

Extra Credit

In this part, because we are trying to find the first height $k$ such that hexagonal packing will always be strictly more efficient than square packing, we are always comparing equal areas between square and hexagonal packing. As a result, we can determine the cutoff point solely from the number of circles rather than needing to divide by the area.

Algorithmically, we can have a running priority queue, which acts as a "race" between the square packing and the hexagonal packing. At the end of each iteration, we add a new row to whichever packing method we're using, putting it into the priority queue based on height, and throwing some other information in there: whether it's square packing (or hexagonal), the number of circles it's accumulated, and the number of rows (which will help us to get an exact answer for hexagonal packing). At each step, we always pick whichever step has the lowest height. We also want to keep track of the most number of circles seen; that way, we can compare how square and hexagonal packing perform as the height increases monotonically.

If hexagonal packing ever outperforms the previous square packing in the number of circles, we can keep track of a running streak. At some point, because hexagonal rows are more efficient, there will be two hexagonal rows happening at once. If this ever happens twice, and the hexagonal packing is better the whole time, then we know the first time it happened must be the minimum height $k$. Let's pick 10 as the streak requirement.

import heapq

pq = [(2.0, False, 4, 1), (2.0, True, 4, 1)]
heapq.heapify(pq)

hex_streak = 0
most_circles = 0
cutoff = pq[0]  # arbitrary starting value

while hex_streak < 10:  # guarantee that both even and odd rows are within the streak
    h, square, circles, rows = curr = heapq.heappop(pq)
    if square:
        if circles >= most_circles:
            hex_streak = 0
            most_circles = circles
        heapq.heappush(pq, (h + 2.0, True, circles + 4, rows + 1))
    else:
        if circles > most_circles:
            if hex_streak == 0:
                cutoff = curr
            hex_streak += 1
            most_circles = circles
        next_row_circles = 3 if rows % 2 else 4
        heapq.heappush(pq, (h + 3**0.5, False, circles + next_row_circles, rows + 1))

h, square, circles, rows = cutoff
assert not square
print(f'# of circles\t{circles}')
print(f'# of rows\t{rows}')
print(f'Height (approx)\t{h:f}')
print(f'Height (exact)\t2 + {rows - 1}*sqrt(3)')

Output:

# of circles    368
# of rows       105
Height (approx) 182.133284
Height (exact)  2 + 104*sqrt(3)

Looks like starting at a height of $2+104\sqrt3$ (about $182.1333$), with 105 rows of 368 circles, hexagonal packing will always be better.

How come we can stop at a streak of 10? Well, really, we can probably stop at 8, but because increasing this cutoff doesn't make change the answer, I thought it'd be safe to throw in some extra in case there was an off-by-one (or off-by-two) error I didn't consider. Changing the cutoff to 12, 1000, or $10^6$ yields the same result. And 8 would work because of the ratio of $\sqrt3$ with $2$ being just over $\frac{6}{7}$, meaning each row of hexagonal packing accumulates a height difference of less than $\frac{1}{7}$ with square packing. Thus, the periodicity of seeing double-hex-rows (which, while not rational, is bounded between 6 and 7) just works out in a way where this streak requirement is sufficient.

If we peek at the values near the end of the iteration, we can see these:

(180.0, True, 360, 90)
(180.40123317959421, False, 364, 104)
(182.0, True, 364, 91)                 # Square packing is as good as the hexagonal packing, resetting the hex streak
(182.13328398716308, False, 368, 105)  # Odd row - Hexagonal packing is better again, restarting the streak
(183.86533479473195, False, 371, 106)  # Even row - hexagonal packing is still better
(184.0, True, 368, 92)
(185.59738560230082, False, 375, 107)  # Odd row
(186.0, True, 372, 93)
(187.3294364098697, False, 378, 108)   # Even row
(188.0, True, 376, 94)
(189.06148721743855, False, 382, 109)  # Odd row
(190.0, True, 380, 95)
(190.79353802500742, False, 385, 110)  # Even row
(192.0, True, 384, 96)
(192.5255888325763, False, 389, 111)   # Odd row
(194.0, True, 388, 97)                 # This was square packing's last stand: coming right after an odd row before a set of two hex rows
(194.25763964014516, False, 392, 112)  # Even row
(195.98969044771403, False, 396, 113)  # Odd row - Now that two rows have come, square packing can never be better
(196.0, True, 392, 98)
(197.7217412552829, False, 399, 114)   # Streak of 10 for hexagonal packing - we can stop

(Additional note: We're adding $\sqrt3$ for each hexagonal packing iteration, which, if done enough, will accumulate a lot of floating point error. To be more accurate, we could use the exact formula at each step based on the number of rows, but there was not enough floating point error here to justify the need for that.)

Answer: 2 + 104sqrt(3) (about 182.1333)