Papers for

computational geometry software teams

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Circle packing minimum radius grows quadratically with explicit bounds

Minimum central circles: an effective characterization of the global asymptotic constant

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.

Sat 12 SeptComputational Geometry
The gist
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.
Open → 2609.13630v1