# 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
##### Keywords:
packings of equal disks; optimal packings
Full Text: