Circle Packing

How do you fit a handful of identical coins into the smallest possible box? On an infinite floor the answer is famously beautiful: stagger the circles in a honeycomb, and they cover exactly $\frac{\pi}{\sqrt{12}} \approx 90.69\%$ of the plane — a fact conjectured by Thue in 1890 and proved rigorously by László Fejes Tóth in 1940.

But shrink the floor to a finite square and ask for the tightest fit of just n circles, and the tidy honeycomb falls apart. The best known packing of 5 circles has one floating in the center; the best for 7 looks lopsided; many optimal layouts are irregular, off-axis, even chaotic.

That clash — a perfectly neat question with stubbornly messy answers — is the first hint that circle packing is harder than it looks. It is not just an aesthetic curiosity; it is a window into why some optimization problems resist every clever idea we throw at them.

Below is a square with a few equal circles dropped at random — they overlap and spill messily. Press Relax to nudge each circle away from its neighbors and the walls, one small step at a time, while slowly growing the radius. Watch how a clean grid almost never appears; the circles settle into a slightly irregular arrangement instead.

<p class="hint">{{hint}}</p>
<canvas id="cv" width="320" height="320"></canvas>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="relax" type="button">{{btn_relax}}</button>
  <button id="step" type="button" class="ghost">{{btn_step}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
#cv { background: #f3f6f9; border: 1px solid #cdd9e3; border-radius: 10px; display: block;
      width: 320px; max-width: 100%; height: auto; touch-action: none; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; color: #1d3557; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

This is local search: every step only improves things a little, based on what is nearby. It quickly finds a good packing, but it has no idea whether a better one exists — and for many counts of circles, the truly optimal layout looks nothing like what local nudging discovers. Verifying a packing is easy (just check no two circles overlap); proving it is the best possible is the hard part.

How hard is circle packing, really?

• Checking a candidate layout is easy: confirm that no two circles overlap and all sit inside the container — a handful of distance comparisons.
• Optimizing is brutal. The circles' centers are continuous coordinates, the constraints are nonlinear, and the landscape is riddled with local optima — neat-looking packings that no small nudge can improve, yet which are not the global best.
• It's NP-hard. Deciding whether a set of circles of given sizes can be packed into a container is NP-hard in general — it embeds combinatorial packing problems closely related to bin packing. There is no known efficient algorithm, and finding one would settle P vs NP.
• Optimal answers are rare and hard-won. The best packings of n equal circles in a square are proven optimal only for small n (and even then via heavy, computer-assisted proofs); for most larger n we only have best-known layouts, catalogued at sites like Packomania, with no proof they cannot be beaten.

That is the punchline: the smooth, symmetric question hides a rugged search space. The irregular, off-center arrangements are not sloppiness — they are what optimality actually looks like when geometry refuses to be tidy.

"Fit as much round stuff as possible into a limited space" is a surprisingly universal problem:

• Manufacturing and cutting: stamping circular blanks from a sheet of metal, fabric, or wood is a packing problem — every wasted gap costs material, a cousin of bin packing.
• Telecommunications: placing cell towers or Wi-Fi access points so coverage circles blanket an area with the fewest overlaps and gaps.
• Material science and the Kepler conjecture: how densely spheres pack in 3D was Kepler's 400-year-old question, settled (with computer help) by Hales — see the Kepler conjecture.
• Logistics and design: arranging pipes in a conduit, cables in a duct, or seeds in a tray all ask the same "how tight can it go?" question.

Learn why circle packing is hard and you have met continuous optimization with hard local optima — the same obstacle that shows up across science and engineering whenever geometry and efficiency collide.

Circle packing teaches a humbling lesson: the cleanest-looking questions can have the messiest answers. On an infinite plane the honeycomb wins with a tidy 90.69%, proven long ago. Inside a finite square the optimum scatters into irregular, off-axis clusters — and proving any of them best is so hard that it has only been done for small numbers of circles, often with a computer's help.

So the next time a packing looks oddly lopsided, remember: that asymmetry may be optimal, and confirming it sits in the same hard family as P vs NP. Sometimes the universe's best arrangement is simply not the one that looks neat.