×

Minimum perimeter rectangles that enclose congruent non-overlapping circles. (English) Zbl 1185.52015

Dense packings of congruent circles have been extensively studied along the years for various geometric shapes including squares, circles, and equilateral triangles. For rectangles – the focus of the current paper – the present authors have earlier considered minimizing the area for a fixed number \(n\) of congruent circles [Algorithms Comb. 25, 633–650 (2003; Zbl 1077.52511)]. Here, however, the rectangle perimeter is minimized instead. The optimal packings for these two versions of the problem may indeed differ.
The authors use computer simulations to try to find as good packings as possible for up to 5000 circles. Properties of the best packings found are studied in great detail. It is among other things proved that the height-to-width ratio of rectangles with minimum perimeter tends to 1 as the number of congruent circles tends to infinity.

MSC:

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

Citations:

Zbl 1077.52511
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Folkman, J. H.; Graham, R. L., A packing inequality for compact convex subsets of the plane, Canad. Math. Bull., 12, 745-752 (1969) · Zbl 0189.22903
[2] Graham, R. L.; Lubachevsky, B. D., Dense packings of equal disks in an equilateral triangle: From 22 to 34 and beyond, Electron. J. Combin., 3, #A1 (1995), Also see: · Zbl 0817.52020
[3] Graham, R. L.; Lubachevsky, B. D., Repeated patterns of dense packings of equal disks in a square, Electron. J. Combin., 3, 1, #R16 (1996), Also see:
[4] Lubachevsky, B. D.; Graham, R. L., Dense packings of congruent circles in rectangles with a variable aspect ratio, (Aronov, B.; etal., Discrete and Computational Geometry. The Goodman-Pollack Festschrift (2003), Springer), Also see: · Zbl 1077.52511
[5] Nurmela, K. J.; Östergård, P. R.J., Packing up to 50 equal circles in a square, Discrete Comput. Geom., 18, 111-120 (1997) · Zbl 0880.90116
[6] Nurmela, K. J.; Östergård, P. R.J., (Alavi, Y.; Lick, D. R.; Schwenk, Optimal Packings of Equal Circles in na Square. Optimal Packings of Equal Circles in na Square, Combinatorics, Graph Theory, and Algorithms, vol. II (1999), New Issues Press: New Issues Press Kalamazoo) · Zbl 0931.05019
[7] Nurmela, K. J.; Östergård, P. R.J., More optimal packings of equal circles in a square, Discrete Comput. Geom., 22, 439-457 (1999) · Zbl 0931.05019
[8] Nurmela, K. J.; Östergård, P. R.J.; aus dem Spring, R., Asymptotic behavior of optimal circle packings in a square, Canad. Math. Bull., 42, 380-385 (1999) · Zbl 0938.52015
[9] Oler, N., A finite packing problem, Canad. Math. Bull., 4, 153-155 (1961) · Zbl 0101.40301
[10] www.pack-any-shape.com; www.pack-any-shape.com
[11] Ruda, M., The packing of circles in rectangles (Hungarian. English summary), Magyar Tud. Akad. Mat. Fiz. Tud. Oszt., Közl., 19, 73-87 (1970)
[12] www.packomania.com; www.packomania.com
[13] Szabo, P. G.; Markot, M. Cs.; Csendes, T., Global optimization in geometry - circle packing into the square, (Audet, C.; Hansen, P.; Savard, G. S., Essays and Surveys in Global Optimization (2005), Kluwer: Kluwer Dordrecht), 233-266, Also see · Zbl 1136.90445
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.