×

zbMATH — the first resource for mathematics

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
PDF BibTeX XML Cite
Full Text: EMIS EuDML arXiv