This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Addis, B. Articles by Schoen, F. Search for Related Content

Disk Packing in a Square: A New Global Optimization Approach

Dipartimento di Sistemi e Informatica, Università di Firenze, I-50139 Firenze, Italy
Dipartimento di Informatica, Università di Torino, I-10149 Torino, Italy
Dipartimento di Sistemi e Informatica, Università di Firenze, I-50139 Firenze, Italy
b.addis{at}ing.unifi.it
locatell{at}di.unito.it
fabio.schoen{at}unifi.it

We present a new computational approach to the problem of placing n identical nonoverlapping disks in the unit square in such a way that their radii are maximized. The problem has been studied in a large number of papers, from both a theoretical and a computational point of view. In this paper, we conjecture that the problem possesses a so-called funneling landscape, a feature that is commonly found in molecular conformation problems. Based on this conjecture, we develop a stochastic search algorithm that displays excellent numerical performance. Thanks to this algorithm, we could improve over previously known putative optima in the range n 130 in as many as 32 instances, the smallest of which is n = 53.

Key words: disk packing; circle packing; continuous dispersion problem; basin hopping; global optimization; stochastic methods
History: received October 2005; revised June 2006; accepted December 2007.