Boll, W. David; Donovan, Jerry; Graham, Ronald L.; Lubachevsky, Boris D. 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\). Reviewer: Patric Östergård (Helsinki) Cited in 21 Documents 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 Keywords:packings of equal disks; optimal packings Citations:Zbl 0716.68094 PDFBibTeX XMLCite \textit{W. D. Boll} et al., Electron. J. Comb. 7, No. 1, Research paper R46, 9 p. (2000; Zbl 0962.52004) Full Text: arXiv EuDML EMIS