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.

Related papers:

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.

Software:

The current version is circpack 1.3, 23-01-2005.
Downloads:
- 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.