Circle packing minimum radius grows quadratically with explicit bounds
Minimum central circles: an effective characterization of the global asymptotic constant
Computational Geometry
Summary
The paper studies how to arrange circles of increasing sizes around a central circle so that none overlap, and finds a formula that describes how the smallest possible radius of this central circle grows as the number of surrounding circles increases. The authors show this smallest radius scales roughly with the square of the number of circles and provide a way to calculate the exact growth constant using linear programs. They also clarify previous guesses about this growth factor, showing some were incorrect, and open up further questions about a simpler exact formula and the structure behind these packings.
What this means in practice
- •For geometric algorithm developers: Provide explicit bounds and testable formulations for circle packing problems important in layout and spatial optimization tasks.
- •For computational geometry software teams: Incorporate systematic linear program reductions to verify circle placement constraints in dense packing simulations.
A theory result. No direct application yet.
Authors
Maurizio Falconi
Abstract
Let ${R^\ast}(n)$ be the least radius of a central circle to which nonoverlapping circles of radii $1,\ldots,n$ are externally tangent. We prove that ${R^\ast}(n)={C_\ast} n^2+o(n^2)$ and characterize ${C_\ast}$ by finite linear programs with an explicit error tending to zero. The reduction preserves arbitrary orders and all pairwise constraints: the limiting problem places marked points on a line at pairwise separation at least the geometric mean of their marks. Concatenation with a bounded boundary cost proves existence, and balanced finite-word programs supply matching effective upper and lower bounds. Their certified gap is $(1/k+1/r)/π$, before directed arithmetic error, for $k$ mark types and words of length $r$. A quantitative reflected-block recovery theorem supplies genuine permutations and full ring geometry, with a countable extension and a strict four-block improvement. The explicit interval is $C_{\mathrm{term}}+η_{\mathrm{width}}\le{C_\ast}\le U_4$; neither endpoint is asserted sharp. In particular, the coefficient $1/8$ proposed in the preceding finite study is false. An elementary expression for ${C_\ast}$, efficient high-precision evaluation and global floating-circle structure remain open.