The Real Complexity of Circle Packing

Introduction

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.

Pack Them Tighter

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">A few equal circles are dropped at random inside the square — they overlap messily. Press <b>Relax</b> to nudge each circle away from its neighbors and the walls while slowly growing the radius. A clean grid almost never appears; the packing settles into a slightly irregular arrangement instead.</p>
<canvas id="cv" width="320" height="320"></canvas>
<div class="status" id="status">Drop circles, then relax.</div>
<div class="btns">
  <button id="relax" type="button">Relax (×40 steps)</button>
  <button id="step" type="button" class="ghost">One step</button>
  <button id="reset" type="button" class="ghost">New random drop</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Circle packing by RELAXATION (local search). N equal circles live in a square.
    // Each step: (1) push overlapping pairs apart, (2) push circles inside the walls,
    // (3) if the layout is feasible (no overlaps, all inside), grow the radius a touch.
    // Checking a layout is O(N^2) distance tests; finding the OPTIMAL packing is NP-hard,
    // and the result here is a LOCAL optimum that is usually irregular, not a tidy grid.
const cv = document.getElementById('cv'), ctx = cv.getContext('2d');
const W = 320, N = 7;                 // square side, number of circles
let circles = [], r = 16, dr = 1.5;   // radius and current growth step

function reset(){
  r = 16; dr = 1.5; circles = [];
  for (let i = 0; i < N; i++)
    circles.push({ x: r + Math.random()*(W-2*r), y: r + Math.random()*(W-2*r) });
  setStatus(fmt('Dropped %N% circles. Press Relax.', { N: N }), '');
  draw();
}

// True iff no two circles overlap and every circle is fully inside the square.
function feasible(rad){
  for (const c of circles){
    if (c.x < rad-0.01 || c.x > W-rad+0.01 || c.y < rad-0.01 || c.y > W-rad+0.01) return false;
  }
  for (let i = 0; i < N; i++) for (let j = i+1; j < N; j++){
    const dx = circles[i].x-circles[j].x, dy = circles[i].y-circles[j].y;
    if (dx*dx + dy*dy < (2*rad)*(2*rad) - 0.01) return false;
  }
  return true;
}

// Smallest gap (negative = overlap) over all pairs and walls, at radius rad.
function tightness(rad){
  let m = Infinity;
  for (const c of circles) m = Math.min(m, c.x-rad, W-rad-c.x, c.y-rad, W-rad-c.y);
  for (let i = 0; i < N; i++) for (let j = i+1; j < N; j++){
    const dx = circles[i].x-circles[j].x, dy = circles[i].y-circles[j].y;
    m = Math.min(m, Math.hypot(dx, dy) - 2*rad);
  }
  return m;
}

function separate(){
  // Push overlapping pairs apart, then push circles back inside the walls. Iterate
      // until the layout stops moving (converged) or a pass cap is hit, so the resulting
      // tightness reading is trustworthy and the grow/shrink decision below is sound.
  for (let pass = 0; pass < 120; pass++){
    let moved = 0;
    for (let i = 0; i < N; i++) for (let j = i+1; j < N; j++){
      const a = circles[i], b = circles[j];
      let dx = b.x-a.x, dy = b.y-a.y, d = Math.hypot(dx, dy) || 0.001;
      const overlap = 2*r - d;
      if (overlap > 0){
        const ux = dx/d, uy = dy/d, push = overlap/2;
        a.x -= ux*push; a.y -= uy*push; b.x += ux*push; b.y += uy*push;
        moved = Math.max(moved, overlap);
      }
    }
    for (const c of circles){
      c.x = Math.max(r, Math.min(W-r, c.x));
      c.y = Math.max(r, Math.min(W-r, c.y));
    }
    if (moved < 0.02) break;   // converged
  }
}

function step(){
  // RELAX, then ADAPTIVELY GROW. Spread the circles so none overlap, then try to
      // inflate the shared radius by the current step `dr`. If the bigger circles still
      // fit after the layout re-settles, keep the growth; if not, undo it and halve the
      // step. The radius homes in on the tightest feasible packing (a binary search on
      // size) and the layout you see is always a valid, overlap-free packing.
  separate();
  if (dr > 0.05 && r + dr <= W/2){
    const saved = circles.map(c => ({ x: c.x, y: c.y }));
    r += dr; separate();
    if (tightness(r) < -0.05){ r -= dr; circles = saved; dr *= 0.5; } // too greedy: back off
  }
  draw();
}

function relax(){
  for (let k = 0; k < 40; k++) step();
  const ok = feasible(r);
  setStatus(fmt('%v%Settled at radius %r% — %v2%', { v: ok ? '✓ ' : '', r: r.toFixed(1), v2: ok ? 'a valid (locally optimal) packing.' : 'still resolving overlaps...' }),
            ok ? 'ok' : 'bad');
  console.log('radius', r.toFixed(2), 'feasible', ok);
}

function draw(){
  ctx.clearRect(0,0,W,W);
  ctx.strokeStyle = '#cdd9e3'; ctx.strokeRect(0.5,0.5,W-1,W-1);
  for (const c of circles){
    ctx.beginPath(); ctx.arc(c.x, c.y, r, 0, 7);
    ctx.fillStyle = 'rgba(29,53,87,0.18)'; ctx.fill();
    ctx.lineWidth = 2; ctx.strokeStyle = '#1d3557'; ctx.stroke();
    ctx.beginPath(); ctx.arc(c.x, c.y, 2, 0, 7); ctx.fillStyle = '#1d3557'; ctx.fill();
  }
}

function setStatus(t, cls){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status '+cls; }
document.getElementById('relax').addEventListener('click', relax);
document.getElementById('step').addEventListener('click', step);
document.getElementById('reset').addEventListener('click', reset);
reset();

<p class="hint">A few equal circles are dropped at random inside the square — they overlap messily. Press <b>Relax</b> to nudge each circle away from its neighbors and the walls while slowly growing the radius. A clean grid almost never appears; the packing settles into a slightly irregular arrangement instead.</p>
<canvas id="cv" width="320" height="320"></canvas>
<div class="status" id="status">Drop circles, then relax.</div>
<div class="btns">
  <button id="relax" type="button">Relax (×40 steps)</button>
  <button id="step" type="button" class="ghost">One step</button>
  <button id="reset" type="button" class="ghost">New random drop</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Circle packing by RELAXATION (local search). N equal circles live in a square.
    // Each step: (1) push overlapping pairs apart, (2) push circles inside the walls,
    // (3) if the layout is feasible (no overlaps, all inside), grow the radius a touch.
    // Checking a layout is O(N^2) distance tests; finding the OPTIMAL packing is NP-hard,
    // and the result here is a LOCAL optimum that is usually irregular, not a tidy grid.
const cv = document.getElementById('cv'), ctx = cv.getContext('2d');
const W = 320, N = 7;                 // square side, number of circles
let circles = [], r = 16, dr = 1.5;   // radius and current growth step

function reset(){
  r = 16; dr = 1.5; circles = [];
  for (let i = 0; i < N; i++)
    circles.push({ x: r + Math.random()*(W-2*r), y: r + Math.random()*(W-2*r) });
  setStatus(fmt('Dropped %N% circles. Press Relax.', { N: N }), '');
  draw();
}

// True iff no two circles overlap and every circle is fully inside the square.
function feasible(rad){
  for (const c of circles){
    if (c.x < rad-0.01 || c.x > W-rad+0.01 || c.y < rad-0.01 || c.y > W-rad+0.01) return false;
  }
  for (let i = 0; i < N; i++) for (let j = i+1; j < N; j++){
    const dx = circles[i].x-circles[j].x, dy = circles[i].y-circles[j].y;
    if (dx*dx + dy*dy < (2*rad)*(2*rad) - 0.01) return false;
  }
  return true;
}

// Smallest gap (negative = overlap) over all pairs and walls, at radius rad.
function tightness(rad){
  let m = Infinity;
  for (const c of circles) m = Math.min(m, c.x-rad, W-rad-c.x, c.y-rad, W-rad-c.y);
  for (let i = 0; i < N; i++) for (let j = i+1; j < N; j++){
    const dx = circles[i].x-circles[j].x, dy = circles[i].y-circles[j].y;
    m = Math.min(m, Math.hypot(dx, dy) - 2*rad);
  }
  return m;
}

function separate(){
  // Push overlapping pairs apart, then push circles back inside the walls. Iterate
      // until the layout stops moving (converged) or a pass cap is hit, so the resulting
      // tightness reading is trustworthy and the grow/shrink decision below is sound.
  for (let pass = 0; pass < 120; pass++){
    let moved = 0;
    for (let i = 0; i < N; i++) for (let j = i+1; j < N; j++){
      const a = circles[i], b = circles[j];
      let dx = b.x-a.x, dy = b.y-a.y, d = Math.hypot(dx, dy) || 0.001;
      const overlap = 2*r - d;
      if (overlap > 0){
        const ux = dx/d, uy = dy/d, push = overlap/2;
        a.x -= ux*push; a.y -= uy*push; b.x += ux*push; b.y += uy*push;
        moved = Math.max(moved, overlap);
      }
    }
    for (const c of circles){
      c.x = Math.max(r, Math.min(W-r, c.x));
      c.y = Math.max(r, Math.min(W-r, c.y));
    }
    if (moved < 0.02) break;   // converged
  }
}

function step(){
  // RELAX, then ADAPTIVELY GROW. Spread the circles so none overlap, then try to
      // inflate the shared radius by the current step `dr`. If the bigger circles still
      // fit after the layout re-settles, keep the growth; if not, undo it and halve the
      // step. The radius homes in on the tightest feasible packing (a binary search on
      // size) and the layout you see is always a valid, overlap-free packing.
  separate();
  if (dr > 0.05 && r + dr <= W/2){
    const saved = circles.map(c => ({ x: c.x, y: c.y }));
    r += dr; separate();
    if (tightness(r) < -0.05){ r -= dr; circles = saved; dr *= 0.5; } // too greedy: back off
  }
  draw();
}

function relax(){
  for (let k = 0; k < 40; k++) step();
  const ok = feasible(r);
  setStatus(fmt('%v%Settled at radius %r% — %v2%', { v: ok ? '✓ ' : '', r: r.toFixed(1), v2: ok ? 'a valid (locally optimal) packing.' : 'still resolving overlaps...' }),
            ok ? 'ok' : 'bad');
  console.log('radius', r.toFixed(2), 'feasible', ok);
}

function draw(){
  ctx.clearRect(0,0,W,W);
  ctx.strokeStyle = '#cdd9e3'; ctx.strokeRect(0.5,0.5,W-1,W-1);
  for (const c of circles){
    ctx.beginPath(); ctx.arc(c.x, c.y, r, 0, 7);
    ctx.fillStyle = 'rgba(29,53,87,0.18)'; ctx.fill();
    ctx.lineWidth = 2; ctx.strokeStyle = '#1d3557'; ctx.stroke();
    ctx.beginPath(); ctx.arc(c.x, c.y, 2, 0, 7); ctx.fillStyle = '#1d3557'; ctx.fill();
  }
}

function setStatus(t, cls){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status '+cls; }
document.getElementById('relax').addEventListener('click', relax);
document.getElementById('step').addEventListener('click', step);
document.getElementById('reset').addEventListener('click', reset);
reset();

Result

Console

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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/circle-packing/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Circle Packing

When the neatest-looking problem hides a hard one