×

Optimal packings of congruent circles on a square flat torus. (English) Zbl 1348.52014

The following problem is considered: given \(N\) points find the maximal \(r>0\) such that \(N\) circles of radius \(r\) could be put on the square flat torus \(\mathbb{T}=\mathbb{R}^2/\mathbb{Z}^2\) without overlapping, or, equivalently, to find the maximal \(d>0\) such that there exist \(N\) points on the torus with pairwise distances not less than \(d\) (where \(d=2r\)). The authors found optimal arrangements for \(N=6,7,8\). Surprisingly, in the case \(N=7\) there are 3 different optimal arrangements. The proof is based on a computer enumeration of toroidal irreducible graphs. A modified version of the program Surftri by T. Sulanke was used.

MSC:

52C17 Packing and covering in \(n\) dimensions (aspects of discrete geometry)
52C26 Circle packings and discrete conformal geometry
05C30 Enumeration in graph theory
05B40 Combinatorial aspects of packing and covering

Software:

plantri; Surftri
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Brass, P., Moser, W.O.J., Pach, J.: Research Problems in Discrete Geometry. Springer, New York (2005) · Zbl 1086.52001
[2] Brinkmann, G., McKay, B.D.: Fast generation of planar graphs. http://cs.anu.edu.au/ bdm/plantri/. Accessed 2012 · Zbl 1039.05531
[3] Connelly, R.: Juxtapositions rigides de cercles et de spheres. I. Juxtapositions finies. Struct. Topol. (14), 4360 (1988) (Dual French-English text) · Zbl 0725.52009
[4] Connelly, R.: Juxtapositions rigides de cercles et de spheres. II. Juxtapositions infinies de mouvement fini. Struct. Topol. (16), 5776 (1990) (Dual French-English text) · Zbl 0725.52009
[5] Connelly, R.: Rigidity of packings. Eur. J. Comb. 29(8), 1862-1871 (2008) · Zbl 1156.52012 · doi:10.1016/j.ejc.2008.01.009
[6] Connelly, R., Dickinson, W.: Periodic planar disc packings. Philos. Trans. R. Soc. Lond. A 372, 20120039 (2014) · Zbl 1353.52010 · doi:10.1098/rsta.2012.0039
[7] Conway, J.H., Sloane, N.J.A.: Sphere Packings, Lattices and Groups, 2nd edn. Springer, New York (1993) · Zbl 0785.11036 · doi:10.1007/978-1-4757-2249-9
[8] Danzer, L.: Finite point-sets on \[\mathbf{S}^2\] S2 with minimum distance as large as possible. Discrete Math. 60, 3-66 (1986) · Zbl 0644.52007 · doi:10.1016/0012-365X(86)90002-6
[9] Dickinson, W., Guillot, D., Keaton, A., Xhumari, S.: Optimal packings of up to five equal circles on a square flat torus. Beitr. Algebra Geom. 52(2), 315-333 (2011) · Zbl 1231.52013 · doi:10.1007/s13366-011-0029-7
[10] Habicht, W., van der Waerden, B.L.: Lagerungen von Punkten auf der Kugel. Math. Ann. 123, 223-234 (1951) · Zbl 0043.35604 · doi:10.1007/BF02054950
[11] Melissen, J.B.M.: Densest packing of six equal circles in a square. Elem. Math. 49, 27-31 (1994) · Zbl 0807.52013
[12] Musin, O.R., Tarasov, A.S.: The strong thirteen spheres problem. Discrete Comput. Geom. 48, 128-141 (2012) · Zbl 1269.52015 · doi:10.1007/s00454-011-9392-2
[13] Schaer, J.: The densest packing of 9 circles in a square. Can. Math. Bull. 8, 273-277 (1965) · Zbl 0144.44303 · doi:10.4153/CMB-1965-018-9
[14] Schaer, J., Meir, A.: On a geometric extremum problem. Can. Math. Bull. 8, 21-27 (1965) · Zbl 0136.42301 · doi:10.4153/CMB-1965-004-x
[15] Schütte, K., Van der Waerden, B.L.: Auf welcher Kugel haben 5,6,7,8 oder 9 Punkte mit Mindestabstand 1 Platz? Math. Ann. 123, 96-124 (1951) · Zbl 0042.16602 · doi:10.1007/BF02054944
[16] Schütte, K., van der Waerden, B.L.: Das Problem der dreizehn Kugeln. Math. Ann. 125, 325-334 (1953) · Zbl 0050.16701 · doi:10.1007/BF01343127
[17] Sulanke, T.: Generating irreducible triangulations of surfaces. arXiv:math/0606687 · Zbl 1106.05036
[18] Tóth, L.F.: Lagerungen in der Ebene, auf der Kugel und in Raum. Springer, New York (1953). Russian translation, Moscow, 1958 · Zbl 0052.18401 · doi:10.1007/978-3-662-01206-2
[19] Tóth, L.F.: Regular Figures. International Series of Monographs on Pure and Applied Mathematics, vol. 48. Macmillan, New York (1964)
[20] Usikov, D.A.: Optimal circle packings of a flat square torus. Private Communication, 2004
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.