Abstract

Circle packing is a challenging computational problem, which has been studied systematically only for a handful of domains (the disk, the square, the rectangle, regular polygons and few others). Finding the global maximum of the packing fraction becomes increasingly difficult as N (number of disks) grows and proofs of  optimality only exist for special domains and limited N. There is considerable interest, however, in finding good packings in more general domains, because of the multiple applications of packing to different areas of knowledge. We have devised an algorithm that, at least in principle, can be used to obtain densely packed configurations in arbitrary domains (we will only discuss two dimensional examples but the extension to three or even higher dimension is straightforward), which include ellipses with arbitrary eccentricity, rectangles of different proportions, multiply connected domains (for instance a concentric circular annulus), concave domains (for example a cross of varying proportions) and even domains with a singularity on the border (the cardioid). Numerical results for all these cases will be presented. Our algorithm could be applied with minor modifications to study packing configurations in tubular containers or more general containers in three dimensions of arbitrary shape.