Packings of equal circles in a square - the optimality
proofs for 28, 29, and 30 circles are now complete!
The final statement for n=28,29,30:
The packing configurations found by Graham and Lubachevsky (for n=28) and by
Nurmela and Ostergaard (for n=29,30) result in optimal packings of
n circles in the unit square. Furthermore, these packing configurations are
uniquely optimal if we disregard the symmetric cases, and for n=28,29, the
movement of a free circle.
M. Cs. Markót: Optimal Packing of 28 Equal Circles in a Unit Square - the First Reliable Solution.
Numerical Algorithms 37, 253-261, 2004.
A computer-assisted method for n=28
providing high precision guaranteed enclosures for both the global optimizer and the
global optimum value.
M. Cs. Markót and T. Csendes: A New Verified Optimization Technique
for the ``Packing Circles in a Unit Square'' Problems, SIAM J. Optimization
16, 193-219, 2005.
A more detailed description of the
optimality proofs including the basic algorithms and proofs
of correctness. This paper introduces tight enclosures of the optimizers and
optimum values for 28, 29 and 30 circles.
M.Cs. Markót and T. Csendes: A reliable area reduction technique for solving circle packing problems,
Computing 77, 147-162, 2006.
Details of the interval arithmetic-based core
elimination method with proof of correctness and pseudo algorithms.
M.Cs. Markót: Interval Methods for Verifying Structural Optimality of Circle
Packing Configurations in the Unit Square.
J. Computational and Applied Mathematics 199, 353-357, 2007.
The final part: determining structural, geometric properties
of the optimal packings, using the previous numerical results.
- The current version is circpack 1.3, 23-01-2005.
- circpack_1.3.tgz (size: 13 MB): the full
package including all the source codes, extensive html and PostScript
documentations, and many intermediate and final results. (The total
set of compressed outputs takes a whole CD...)
- README.ps: requirements, installation instructions,
and a guide to reproduce to original study results.
- Only for historical reasons: an earlier
version (circpack 1.1, as of 17-03-2003) of the optimization code.
Mihály Csaba Markót, 08-11-2005.