On the Packing of Cubes and Other Objects

Bálint, Vojtech   ; Sedliačková, Zuzana   ; Adamko, Peter

Pokroky matematiky, fyziky a astronomie, Tome 65 (2020) no. 2, pp. 61-75

Résumé (VO)

Uvedieme históriu a prehľad výsledkov o ukladaní kociek do kvádra s minimálnym objemom a pridáme aj hlavné myšlienky niektorých dôkazov. V závere sa veľmi stručne zmienime o iných ukladacích problémoch.

Détail

Classification : 52C15, 52C17

Bibliographie

[1] Adamko, P.: On the volume of points at distance at least 1 in the unit four-dimensional cube. J. Geom. Graph. 23 (2019), 1–3. | MR

[2] Adamko, P., Bálint, V.: Universal asymptotical results on packing of cubes. Stud. Univ. Žilina Math. Ser. 28 (2016), 5–16.

[3] Ament, P., Blind, G.: Packing equal circles in a square. Studia Sci. Math. Hungar. 36 (2000), 313–316. | MR

[4] Andreescu, T., Mushkarov, O.: A note on the Malfatti problem. Math. Reflections 4 (2006), 1–7.

[5] Anstreicher, K. M.: The thirteen spheres: A new proof. Discrete Comput. Geom. 31 (2004), 613–625. | DOI | MR

[6] Bálint, V.: Poznámka k jednému ukladaciemu problému. Práce a Štúdie Vysokej školy dopravy a spojov v Žiline, séria Mat.–Fyz. 8 (1990), 7–12.

[7] Bálint, V.: A packing problem and the geometrical series. In: Nešetřil, J., Fiedler, M. (eds.): Fourth Czechoslovakian symposium on combinatorics, graphs and complexity, held in Prachatice, Czechoslovakia, 1990. Proceedings. Annals of Discrete Mathematics, vol. 51. North-Holland, Amsterdam, 1992, 17–21. | MR

[8] Bálint, V.: Two packing problems. Discrete Math. 178 (1998), 233–236. | DOI | MR

[9] Bálint, V.: Maximization of the sum of areas. Stud. Univ. Žilina Math. Ser. 24 (2010), 1–8. | MR

[10] Bálint, V.: Dva typy najlepších uložení systému štvorcov v obdĺžniku. Proceedings of Symposium on Computer Geometry, STU, Bratislava, 2011, 13–16.

[11] Bálint, V., Adamko, P.: Minimalizácia objemu kvádra pre uloženie troch kociek v dimenzii 4. G, Slov. Čas. Geom. Graf. 12 (2015), 5–16.

[12] Bálint, V., Adamko, P.: Minimization of the container for packing of three cubes in dimension 4. Proceedings of Slovak–Czech Conference on Geometry and Graphics, STU, Bratislava, 2015, 13–24.

[13] Bálint, V., Adamko, P.: Minimization of the parallelepiped for packing of three cubes in dimension 6. Proceedings of APLIMAT 2016 – 15th Conference on Applied Mathematics, Bratislava, 2016, 44–55.

[14] Bálint, V., Bálint, V., jr.: Unicity of one optimal arrangement of points in the cube. Proceedings of Symposium on Computer Geometry, Bratislava, 2001, 8–10.

[15] Bálint, V., Bálint, V., jr.: On the volume of points at distance at least one in the unit cube. Geombinatorics 12 (2003), 157–166. | MR

[16] Bálint, V., Bálint, V., jr.: Horný odhad pre rozmiestňovanie bodov v kocke. Sborník 5. konference o matematice a fyzice na VŠT, Brno, 2007, 32–35.

[17] Bálint, V., Bálint, V., jr.: On the maximum volume of points at least one unit away from each other in the unit $n$-cube. Periodica Math. Hung. 57 (2008), 83–91. | DOI | MR

[18] Bálint, V., Bálint, V., jr.: Umiestňovnie bodov do jednotkovej kocky. G, Slov. Čas. Geom. Graf. 5 (2008), 5–12.

[19] Bálint, V., Bálint, V., jr.: Placing of points into the 5-dimensional unit cube. Period. Math. Hungar. 65 (2012), 1–16. | DOI | MR

[20] Bálint, V., Bálint, V., jr.: Packing of points into the unit 6-dimensional cube. Contrib. Discrete Math. 7 (2012), 51–57. | MR

[21] Bálint, V., Kaukič, M., Peško, Š.: Solving one maximization problem using a computer. Abstracts of the 3rd Croatian Conference on Geometry and Graphics, http://www.grad.hr/sgorjanc/supetar/abstracts.pdf

[22] Bezdek, A., Fodor, F.: Extremal triangulations of convex polygons. Symmetry: Culture and Science 21 (2010), 333–340.

[23] Böröczky, K.: The Newton-Gregory problem revisited. In: Bezdek, A. (ed.): Discrete Geometry, Marcel Dekker, New York, 2003, 103–110. | MR

[24] Böröczky, K., jr.: Finite packing and covering. Cambridge Univ. Press, 2004. | MR

[25] Brass, P., Moser, W. O. J., Pach, J.: Research problems in discrete geometry. Springer, New York, 2005. | MR

[26] Cohn, H., Elkies, N. D.: New upper bounds on sphere packings I. Ann. of Math. (2) 157 (2003), 689–714. | MR

[27] Croft, H. T., Falconer, K. J., Guy, R. K.: Unsolved problems in geometry. 2nd ed., Springer-Verlag, New York–Berlin–Heidelberg, 1994. | MR

[28] Edel, Y., Rains, E. M., Sloane, N. J. A.: On kissing volumes in dimensions 32 to 128. Electron. J. Combin. 5 (1988), #R22. | MR

[29] Erdős, P.: On some problems of elementary and combinatorial geometry. Ann. Mat. Pura Appl., Ser. IV 103 (1975), 99–108. | DOI | MR

[30] Erdős, P.: Some more problems on elementary geometry. Austral. Math. Soc. Gaz. 5 (1978), 52–54. | MR

[31] Fejes Tóth, L.: Remarks on a theorem of R. M. Robinson. Studia Sci. Math. Hung. 4 (1969), 441–445. | MR

[32] Fejes Tóth, L.: Lagerungen in der Ebene, auf der Kugel und im Raum. 2. Auflage, Springer-Verlag, 2003. | MR

[33] Fejes Tóth, G., Kuperberg, W.: Packing and covering with convex sets. In: Gruber, P. M. et al. (ed.): Handbook of convex geometry, Volume B, North-Holland, Amsterdam, 1993, 799–860. | MR

[34] Ferguson, S. P., Hales, T. C.: The Kepler conjecture: The Hales–Ferguson proof. Springer, New York, 2011. | MR

[35] Fodor, F.: The densest packing of 19 congruent circles in a circle. Geom. Dedicata 74 (1999), 139–145. | DOI | MR

[36] Fodor, F.: The densest packing of 12 congruent circles in a circle. Beitr. Algebra Geom. 21 (2000), 401–409. | MR

[37] Fodor, F.: Packing 14 congruent circles in a circle. Stud. Univ. Žilina Math. Ser. 16 (2003), 25–34. | MR

[38] Fodor, F.: The densest packing of 13 congruent circles in a circle. Beitr. Algebra Geom. 21 (2003), 431–440. | MR

[39] Gauss, C. F.: Recension der Untersuchungen über die Eigenschaften der positiven ternären quadratischen Formen von Ludwig August Seber. J. Reine Angew. Math. 20 (1840), 312–320. | MR

[40] 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 (1995), #A1. | DOI | MR

[41] Graham, R. L., Lubachevsky, B. D., Nurmela, K. J., Östergård, P. R. J.: Dense packings of congruent circles in a circle. Discrete Math. 181 (1998), 139–154. | DOI | MR

[42] Groemer, H.: Covering and packing properties of bounded sequences of convex sets. Mathematica 29 (1982), 18–31. | MR

[43] Guy, R. K.: Problems. In: Kelly, L. M. (ed.): The geometry of metric and linear spaces. Proceedings of a conference held at Michigan State University, East Lansing, June 17–19, 1974, Springer-Verlag, 1975, 233–244. | MR

[44] Hadwiger, H.: Über Treffenzahlen bei translationsgleichen Eikörpen. Arch. Math. 8 (1957), 212–213. | DOI | MR

[45] Hales, T. C.: The sphere packing problem. J. Comput. Appl. Math. 44 (1992), 41–76. | DOI | MR

[46] Hales, T. C.: The status of the Kepler conjecture. Math. Intelligencer 16 (1994), 47–58. | DOI | MR

[47] Hales, T. C.: Sphere packings, I. Discrete Comput. Geom. 17 (1997), 1–51. | DOI | MR

[48] Hales, T. C.: Sphere packings, II. Discrete Comput. Geom. 18 (1997), 135–149. | DOI | MR

[49] Hales, T. C.: Cannonballs and honeycombs. Notices Amer. Math. Soc. 47 (2000), 440–449. | MR

[50] Hales, T. C., Ferguson, S. P.: The Kepler conjecture. Discrete Comput. Geom. 36 (2006), 1–269. | MR

[51] Hortobágyi, I.: Über die Scheibenklassen bezügliche Newtonsche Zahl der konvexen Scheiben. Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 18 (1975), 123–127. | MR

[52] Horvát, G. Á.: Packing points into a unit cube in higher space. Stud. Univ. Žilina Math. Ser. 24 (2010), 23–28. | MR

[53] Hougardy, S.: On packing squares into a rectangle. Tech. Report 101007. Forschungsinstitut für Diskrete Mathematik, March 2010. | MR

[54] Hsiang, W.-Y.: On the sphere packing problem and the proof of Kepler’s conjecture. Internat. J. Math. 4 (1993), 739–831. | DOI | MR

[55] Hsiang, W.-Y.: A rejoinder to T. C. Hales’ article: The status of the Kepler conjecture. Math. Intelligencer 17 (1994), 35–42. | MR

[56] Januszewski, J.: Packing rectangles into a large square. Period. Math. Hungar. 72 (2016), 90–101. | DOI | MR

[57] Jennings, D.: On packing unequal rectangles in the unit square. J. Combin. Theory, Ser. A 68 (1994), 465–469. | DOI | MR

[58] Jennings, D.: On packing of squares and rectangles. Discrete Math. 138 (1995), 293–300. | DOI | MR

[59] Joós, A.: Pontok elhelyezése egységkockában. PhD tézisek, 2008.

[60] Joós, A.: On the volume of points at distance at least 1 in the 5-dimensional unit cube. Acta Sci. Math. 76 (2010), 217–231. | DOI | MR

[61] Joós, A., Bálint, V.: Packing of odd squares revisited. J. Geom. 110 (2019), article no. 10. | DOI | MR

[62] Kabatjanskij, G. A., Levenshtein, V. I.: Bounds for packings on a sphere and space. Problemy Peredachi Informatsii 14 (1978), 3–24. | MR

[63] Kepler, J.: Strena seu de nive sexangula. Tampach, Frankfurt, 1611. English translation: The six-cornered snowflake. Oxford, 1966.

[64] Kleitman, D. J., Krieger, M. M.: Packing squares in rectangles I. Ann. New York Acad. Sci. 175 (1970), 253–262. | DOI | MR

[65] Kleitman, D. J., Krieger, M. M.: An optimal bound for two dimensional bin packing. Proceedings of the 16th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, 1975, 163–168. | MR

[66] Kosiński, A.: A proof of the Auerbach-Banach-Mazur-Ulam theorem on convex bodies. Colloq. Math. 4 (1957), 216–218. | DOI | MR

[67] Leech, J.: The problem of thirteen spheres. Math. Gaz. 40 (1956), 22–23. | DOI | MR

[68] Leech, J.: Some sphere packings in higher space. Canad. J. Math. 16 (1964), 657–682. | DOI | MR

[69] Levenshtein, V. I.: On bounds for packings in $n$-dimensional Euclidean space. Soviet Math. Dokl. 20 (1979), 417–421. | MR

[70] Lubachevsky, B. D., Graham, R. L., Stikkinger, F. H.: Patterns and structures in disk packings. Period. Math. Hungar. 34 (1997), 123–142. | DOI | MR

[71] Malfatti, G.: Memoria sopra un problema sterotomico. Memorie di Matematica e di Fisica della Societa Italiana delle Scienze 10 (1803), 235–244.

[72] Markót, M. Cs.: Optimal packing of 28 equal circles in a unit square – the first reliable solution. Numer. Algorithms 37 (2004), 253–261. | DOI | MR

[73] Mauldin, R. D.: The Scottish Book. Birkhäuser, 1981. | MR

[74] Meir, A., Moser, L.: On packing of squares and cubes. J. Combin. Theory 5 (1968), 126–134. | DOI | MR

[75] Melissen, J. B. M.: Densest packings of congruent circles in an equilateral triangle. Amer. Math. Monthly 100 (1993), 916–925. | DOI | MR

[76] Melissen, J. B. M.: Densest packing of six equal circles in a square. Elem. Math. 49 (1994), 27–31. | MR

[77] Melissen, J. B. M.: Densest packing of eleven congruent circles in a circle. Geom. Dedicata 50 (1994), 15–25. | DOI | MR

[78] Melissen, J. B. M.: Densest packing of eleven congruent circles in an equilateral triangle. Acta Math. 65 (1994), 389–393. | MR

[79] Melissen, J. B. M., Schuur, P. C.: Packing 16, 17 or 18 circles in an equilateral triangle. Discrete Math. 145 (1995), 333–342. | DOI | MR

[80] Moon, J., Moser, L.: Some packing and covering theorems. Colloq. Math. 17 (1967), 103–110. | DOI | MR | Zbl

[81] Moser, L.: Poorly formulated unsolved problems of combinatorial geometry. 1963.

[82] Moser, W. O. J.: Problems, problems, problems. Discrete Appl. Math. 31 (1991), 201–225. | DOI | MR

[83] Moser, W. O. J., Pach, J.: Research problems in discrete geometry. McGill University, Montreal, 1986, 1993. | MR

[84] Musin, O. R.: The problem of twenty-five spheres. Russian Math. Surveys 58 (2003), 794–795. | DOI | MR

[85] Musin, O. R.: The kissing volume in four dimensions. Ann. of Math. (2) 168 (2008), 1–32. | MR

[86] Novotný, P.: A note on packing of squares. Studies Univ. Žilina Mat.-Phys. Ser. A 10 (1995), 35–39. | MR

[87] Novotný, P.: On packing of squares into a rectangle. Arch. Math. (Brno) 32 (1996), 75–83. | MR

[88] Novotný, P.: On packing of four and five squares into a rectangle. Note Mat. 19 (1999), 199–206. | MR

[89] Novotný, P.: Využitie počítača pri riešení ukladacieho problému. Proceedings of Symposium on Computational Geometry, STU, Bratislava, 2002, 60–62.

[90] Novotný, P.: Pakovanie troch kociek. Proceedings of Symposium on Computer Geometry, STU, Bratislava, 2006, 117–119.

[91] Novotný, P.: Najhoršie pakovateľné štyri kocky. Proceedings of Symposium on Computer Geometry, STU, Bratislava, 2007, 78–81.

[92] Novotný, P.: Ukladanie kociek do kvádra. Proceedings of Symposium on Computer Geometry, STU, Bratislava, 2011, 100–103.

[93] Nurmela, K. J., Östergård, P. R. J.: More optimal packings of equal circles in a square. Discrete Comput. Geom. 22 (1999), 439–457. | DOI | MR

[94] Odlyzko, A. M., Sloane, N. J. A.: New bounds on the unit spheres that can touch a unit sphere in n-dimensions. J. Combin. Theory Ser. A 26 (1979), 210–214. | DOI | MR

[95] Oler, N.: A finite packing problem. Canad. Math. Bull. 4 (1961), 153–155. | DOI | MR

[96] Paulhus, M.: An algorithm for packing squares. J. Combin. Theory Ser. A 82 (1998), 147–157. | DOI | MR

[97] Payan, Ch.: Empilement de cercles égaux dans un triangle équilatéral. À propos d’une conjecture d’Erdős-Oler. Discrete Math. 165–166 (1997), 555–565. | DOI | MR

[98] Peikert, R., Würtz, D., Monagan, M., de Groot, C.: Packing circles in a square: A review and new results. In: Kall, P. (ed.): System modelling and optimization. Proceedings of the 15th IFIP conference, Zurich, Switzerland, September 2–6, 1991, Springer-Verlag, Berlin, 1992, 45–54. | MR

[99] Pirl, U.: Der Mindestabstand von n in der Einheitskreisscheibe gelegenen Punkten. Math. Nachr. 40 (1969), 111–124. | DOI | MR

[100] Rogers, C. A.: The packing of equal spheres. Proc. Lond. Math. Soc. (3) 8 (1958), 609–620. | DOI | MR

[101] Sedliačková, Z.: Packing three cubes in 8-dimensional space. J. Geom. Graph. 22 (2018), No. 2, 217–223. | MR

[102] Schaer, J.: The densest packing of 9 circles in a square. Canad. Math. Bull. 8 (1965), 273–277. | DOI | MR

[103] Schaer, J.: On the densest packing of spheres in a cube. Canad. Math. Bull. 9 (1966), 265–270. | DOI | MR

[104] Schaer, J., Meir, A.: On a geometric extremum problem. Canad. Math. Bull. 8 (1965), 21–27. | DOI | MR

[105] Schütte, K., van der Waerden, B. L.: Das Problem der dreizehn Kugeln. Math. Ann. 125 (1953), 325–334. | DOI | MR

[106] Thue, A.: On the densest packing of congruent circles in the plane. Skr. Vidensk.-Selsk. Christiana 1 (1910), 3–9. | MR

[107] Vardy, A.: A new sphere packing in 20 dimensions. Invent. Math. 121 (1995), 119–133. | DOI | MR

[108] Zalgaller, V. A., Los, G. A.: The solution of Malfatti’s problem. J. Math. Sci. (N.Y.) 72 (1994), 3163–3177. | DOI | MR

[109] Zong, C.: The kissing volumes of convex bodies – a brief survey. Bull. Lond. Math. Soc. 30 (1998), 1–10. | DOI | MR