×

Improving dense packings of equal disks in a square. (English) Zbl 0962.52004

Electron. J. Comb. 7, No. 1, Research paper R46, 9 p. (2000); printed version J. Comb. 7, No. 2 (2000).
The problem of maximizing the size of \(n\) nonoverlapping equal disks in a unit square is considered (this problem is equivalent to maximizing the minimum pairwise distance between \(n\) points in a unit square), and a new heuristic for finding good such packings is presented. This heuristic involves the billiards algorithm by B. D. Lubachevsky [J. Comput. Phys. 94, No. 2, 255-283 (1991; Zbl 0716.68094)]. Computational experiments show that the new heuristic is more effective than the billiards algorithm alone. Record-breaking packings are obtained for \(n=32,37,48,50\).

MSC:

52C15 Packing and covering in \(2\) dimensions (aspects of discrete geometry)
05B40 Combinatorial aspects of packing and covering
90C59 Approximation methods and heuristics in mathematical programming

Citations:

Zbl 0716.68094
PDFBibTeX XMLCite
Full Text: arXiv EuDML EMIS