Disk Packing in a Square: A New Global Optimization Approach

Bernardetta Addis (b.addising.unifi.it)
Marco Locatelli (locatelldi.unito.it)
Fabio Schoen (schoening.unifi.it)

Abstract: We present a new computational approach to the problem of placing $n$ identical non overlapping disks in the unit square in such a way that their radius is maximized. The problem has been studied in a large number of papers, both from a theoretical and from a computational point of view. In this paper we conjecture that the problem possesses a so-called funneling landscape, a feature which is commonly found in molecular conformation problems. Based upon this conjecture we develop a stochastic search algorithm which displays excellent numerical performance. Thanks to this algorithm we could improve over previously known putative optima in the range $n \leq 130$ in as many as 32 instances, the smallest of which is $n=53$. First experiments in the related problem of packing equal spheres in the unit cube led us to an improvement for $n=28$ spheres.

Keywords: disk packing, circle packing, sphere packing, basin hopping, global optimization, stochastic methods

Category 1: Global Optimization

Category 2: Global Optimization (Stochastic Approaches )

Citation:

Download: [PDF]

Entry Submitted: 10/12/2005
Entry Accepted: 10/12/2005
Entry Last Modified: 10/14/2005

Modify/Update this entry