×

Dense packings of congruent circles in a circle. (English) Zbl 0901.52017

Two methods based on the maximization of the minimum pairwise distance \(d\) among \(n\) points spread in a circle are proposed to generate packings of congruent circles in the circle. To overcome the difficulty caused by the nonsmoothness of that objective function, in the first method it is approximated by a smooth one, which can be regarded as a potential energy relative to repulsion forces between the points. The second method simulates the movement of the circles as billiard balls inside a circle enlarged so as to force all centers to belong to the original circle; as disks move, \(d\) is increased and a packing is obtained in the limit.
Pictures showing the best known packings of 21-65 circles, as well as a table listing the properties of the best packings of 2-65 circles, are provided.

MSC:

52C15 Packing and covering in \(2\) dimensions (aspects of discrete geometry)
05B40 Combinatorial aspects of packing and covering
90C99 Mathematical programming

Software:

INTBIS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Clare, B. W.; Kepert, D. L., The closest packing of equal circles on a sphere, (Proc. Roy. Soc. London Ser. A, 405 (1986)), 329-344 · Zbl 0586.52008
[2] Conway, J. H.; Sloane, N. J.A., Sphere Packings, Lattices and Groups (1993), Springer: Springer New York · Zbl 0785.11036
[3] Croft, H. T.; Falconer, K. J.; Guy, R. K., Unsolved Problems in Geometry (1991), Springer: Springer New York · Zbl 0748.52001
[4] Fejes Tóth, L., Lagerungen in der Ebene, auf der Kugel und im Raum (1972), Springer: Springer Berlin · Zbl 0052.18401
[5] Goldberg, M., Packing of 14, 16, 17 and 20 circles in a circle, Math. Mag., 44, 134-139 (1971) · Zbl 0212.54504
[6] Graham, R. L., Sets of points with given minimum separation (Solution to Problem E1921), Amer. Math. Monthly, 75, 192-193 (1968)
[7] Graham, R. L.; Lubachevsky, B. D., Dense packings of equal disks in an equilateral triangle: from 22 to 34 and beyond, Electron. J. Combin., 2, A1, 39 (1995), (electronic) · Zbl 0817.52020
[8] Graham, R. L.; Sloane, N. J.A., Penny-packing and two-dimensional codes, Discrete Comput. Geom., 5, 1-11 (1990) · Zbl 0686.52010
[9] Kearfott, R. B.; Novoa, M., Algorithm 681: INTBIS, a portable interval Newton/bisection package, ACM Trans. Math. Software, 16, 152-157 (1990) · Zbl 0900.65152
[10] Kravitz, S., Packing cylinders into cylindrical containers, Math. Mag., 40, 65-71 (1967) · Zbl 0192.28801
[11] Lubachevsky, B. D., How to simulate billiards and similar systems, J. Comput. Phys., 94, 255-283 (1991) · Zbl 0716.68094
[12] B.D. Lubachevsky, R.L. Graham, Curved hexagonal packings of equal disks in a circle, Discrete Comput. Geom., to appear.; B.D. Lubachevsky, R.L. Graham, Curved hexagonal packings of equal disks in a circle, Discrete Comput. Geom., to appear. · Zbl 0881.52010
[13] Melissen, H., Densest packing of eleven congruent circles in a circle, Geom. Dedicata, 50, 15-25 (1994) · Zbl 0810.52013
[14] Melissen, H.; Schuur, P. C., Packing 16, 17 or 18 circles in an equilateral triangle, Discrete Math., 145, 333-342 (1995) · Zbl 0836.52006
[15] Nurmela, K. J., Constructing spherical codes by global optimization methods, (Research Report A32 (1995), Digital Systems Laboratory, Helsinki University of Technology)
[16] K.J. Nurmela, P.R.J. Östergárd, Packing up to 50 equal circles in a square, Discrete Comput. Geom., to appear.; K.J. Nurmela, P.R.J. Östergárd, Packing up to 50 equal circles in a square, Discrete Comput. Geom., to appear. · Zbl 0880.90116
[17] Pirl, U., Der Mindestabstand von \(n\) in der Einbeitskreisscheibe gelegenen Punkten, Math. Nachr., 40, 111-124 (1969) · Zbl 0182.25102
[18] Reis, G. E., Dense packing of equal circles within a circle, Math. Mag., 48, 33-37 (1975) · Zbl 0297.52014
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.