{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:35:42Z","timestamp":1760441742051,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,9,15]],"date-time":"2022-09-15T00:00:00Z","timestamp":1663200000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,9,15]],"date-time":"2022-09-15T00:00:00Z","timestamp":1663200000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["FE407\/17-2"],"award-info":[{"award-number":["FE407\/17-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We provide a tight result for a fundamental problem arising from packing disks into a circular container: The critical density of packing disks in a disk is\u00a00.5. This implies that any set of (not necessarily equal) disks of total area <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\delta \\le 1\/2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03b4<\/mml:mi>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> can always be packed into a disk of area\u00a01; on the other hand, for any <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varepsilon &gt;0$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>&gt;<\/mml:mo>\n                    <mml:mn>0<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> there are sets of disks of area <jats:inline-formula><jats:alternatives><jats:tex-math>$$1\/2+\\varepsilon $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> that cannot be packed. The proof uses a careful manual analysis, complemented by a minor automatic part that is based on interval arithmetic. Beyond the basic mathematical importance, our result is also useful as a blackbox lemma for the analysis of recursive packing algorithms.<\/jats:p>","DOI":"10.1007\/s00454-022-00422-8","type":"journal-article","created":{"date-parts":[[2022,9,15]],"date-time":"2022-09-15T16:14:56Z","timestamp":1663258496000},"page":"51-90","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Packing Disks into Disks with Optimal Worst-Case Density"],"prefix":"10.1007","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9062-4241","authenticated-orcid":false,"given":"S\u00e1ndor P.","family":"Fekete","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Phillip","family":"Keldenich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Scheffer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,9,15]]},"reference":[{"key":"422_CR1","unstructured":"Becker, A.T., Fekete, S.P., Keldenich, Ph., Morr, S., Scheffer, Ch.: Packing geometric objects with optimal worst-case density. In: 35th International Symposium on Computational Geometry (Portland 2019). Leibniz Int. Proc. Inform., vol. 129, #\u00a063. Leibniz-Zent. Inform., Wadern (2019). Video available via https:\/\/www.youtube.com\/watch?v=QpyjB8c4Ngk"},{"issue":"3","key":"422_CR2","doi-asserted-by":"publisher","first-page":"786","DOI":"10.1016\/j.ejor.2007.01.054","volume":"191","author":"I Castillo","year":"2008","unstructured":"Castillo, I., Kampas, F.J., Pint\u00e9r, J.D.: Solving circle packing problems by global optimization: numerical results and industrial applications. Eur. J. Oper. Res. 191(3), 786\u2013802 (2008)","journal-title":"Eur. J. Oper. Res."},{"key":"422_CR3","unstructured":"Demaine, E.D., Fekete, S.P., Lang, R.J.: Circle packing for origami design is hard. In: 5th International Meeting on Origami in Science, Mathematics and Education (Singapore 2010), pp. 609\u2013626. CRC Press, Boca Raton (2011)"},{"key":"422_CR4","unstructured":"Fekete, S.P., Keldenich, Ph., Scheffer, Ch.: Packing disks into disks with optimal worst-case density. In: 35th International Symposium on Computational Geometry (Portland 2019). Leibniz Int. Proc. Inform., vol. 129, #\u00a035. Leibniz-Zent. Inform., Wadern (2019)"},{"issue":"3","key":"422_CR5","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1007\/s00454-018-0020-2","volume":"61","author":"SP Fekete","year":"2019","unstructured":"Fekete, S.P., Morr, S., Scheffer, Ch.: Split packing: algorithms for packing circles with optimal worst-case density. Discrete Comput. Geom. 61(3), 562\u2013594 (2019)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"422_CR6","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1023\/A:1005091317243","volume":"74","author":"F Fodor","year":"1999","unstructured":"Fodor, F.: The densest packing of 19 congruent circles in a circle. Geom. Dedicata 74(2), 139\u2013145 (1999)","journal-title":"Geom. Dedicata"},{"issue":"2","key":"422_CR7","first-page":"401","volume":"41","author":"F Fodor","year":"2000","unstructured":"Fodor, F.: The densest packing of 12 congruent circles in a circle. Beitr\u00e4ge Algebra Geom. 41(2), 401\u2013409 (2000)","journal-title":"Beitr\u00e4ge Algebra Geom."},{"issue":"2","key":"422_CR8","first-page":"431","volume":"44","author":"F Fodor","year":"2003","unstructured":"Fodor, F.: The densest packing of 13 congruent circles in a circle. Beitr\u00e4ge Algebra Geom. 44(2), 431\u2013440 (2003)","journal-title":"Beitr\u00e4ge Algebra Geom."},{"issue":"3","key":"422_CR9","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1016\/0377-2217(94)90410-3","volume":"77","author":"HJ Fraser","year":"1994","unstructured":"Fraser, H.J., George, J.A.: Integrated container loading software for pulp and paper industry. Eur. J. Oper. Res. 77(3), 466\u2013474 (1994)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"422_CR10","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1080\/0025570X.1971.11976122","volume":"44","author":"M Goldberg","year":"1971","unstructured":"Goldberg, M.: Packing of 14, 16, 17 and 20 circles in a circle. Math. Mag. 44(3), 134\u2013139 (1971)","journal-title":"Math. Mag."},{"key":"422_CR11","doi-asserted-by":"crossref","unstructured":"Graham, R.L., Lubachevsky, B.D., Nurmela, K.J., \u00d6sterg\u00e5rd P.R.J.: Dense packings of congruent circles in a circle. Discrete Math. 181(1\u20133), 139\u2013154 (1998)","DOI":"10.1016\/S0012-365X(97)00050-2"},{"key":"422_CR12","doi-asserted-by":"crossref","unstructured":"Hifi, M., M\u2019hallah, R.: A literature review on circle and sphere packing problems: models and methodologies. Adv. Oper. Res. 2009, #\u00a0150624 (2009)","DOI":"10.1155\/2009\/150624"},{"issue":"5","key":"422_CR13","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.ipl.2015.12.007","volume":"116","author":"P Hokama","year":"2016","unstructured":"Hokama, P., Miyazawa, F.K., Schouery, R.C.S.: A bounded space algorithm for online circle packing. Inform. Process. Lett. 116(5), 337\u2013342 (2016)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"422_CR14","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1080\/0025570X.1967.11975768","volume":"40","author":"S Kravitz","year":"1967","unstructured":"Kravitz, S.: Packing cylinders into cylindrical containers. Math. Mag. 40(2), 65\u201371 (1967)","journal-title":"Math. Mag."},{"key":"422_CR15","doi-asserted-by":"crossref","unstructured":"Lang, R.J.: A computational algorithm for origami design. In: 12th Annual Symposium on Computational Geometry (Philadelphia 1996), pp. 98\u2013105. ACM, New York (1996)","DOI":"10.1145\/237218.237249"},{"key":"422_CR16","doi-asserted-by":"crossref","unstructured":"Leung, J.Y.-T., Tam, T.W., Wong, C.S., Young, G.H., Chin, F.Y.L.: Packing squares into a square. J. Parallel Distrib. Comput. 10(3), 271\u2013275 (1990)","DOI":"10.1016\/0743-7315(90)90019-L"},{"issue":"2","key":"422_CR17","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/PL00009314","volume":"18","author":"BD Lubachevsky","year":"1997","unstructured":"Lubachevsky, B.D., Graham, R.L.: Curved hexagonal packings of equal disks in a circle. Discrete Comput. Geom. 18(2), 179\u2013194 (1997)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"422_CR18","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BF01263647","volume":"50","author":"H Melissen","year":"1994","unstructured":"Melissen, H.: Densest packings of eleven congruent circles in a circle. Geom. Dedicata 50(1), 15\u201325 (1994)","journal-title":"Geom. Dedicata"},{"key":"422_CR19","doi-asserted-by":"crossref","unstructured":"Miyazawa, F.K., Pedrosa, L.L.C., Schouery, R.C.S., Sviridenko, M., Wakabayashi,\u00a0Y.: Polynomial-time approximation schemes for circle packing problems. In: 22nd European Symposium on Algorithms (Wroc\u0142aw 2014). Lecture Notes in Comput. Sci., vol. 8737, pp. 713\u2013724. Springer, Heidelberg (2014)","DOI":"10.1007\/978-3-662-44777-2_59"},{"key":"422_CR20","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4064\/cm-17-1-103-110","volume":"17","author":"JW Moon","year":"1967","unstructured":"Moon, J.W., Moser, L.: Some packing and covering theorems. Colloq. Math. 17, 103\u2013110 (1967)","journal-title":"Colloq. Math."},{"key":"422_CR21","doi-asserted-by":"crossref","unstructured":"Morr, S.: Split packing: an algorithm for packing circles with optimal worst-case density. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms (Barcelona 2017), pp. 99\u2013109. SIAM, Philadelphia (2017)","DOI":"10.1137\/1.9781611974782.7"},{"key":"422_CR22","doi-asserted-by":"publisher","first-page":"153","DOI":"10.4153\/CMB-1961-018-7","volume":"4","author":"N Oler","year":"1961","unstructured":"Oler, N.: A finite packing problem. Can. Math. Bull. 4, 153\u2013155 (1961)","journal-title":"Can. Math. Bull."},{"key":"422_CR23","doi-asserted-by":"crossref","unstructured":"Peikert, R., W\u00fcrtz, D., Monagan, M., de Groot, C.: Packing circles in a square: a review and new results. In: System Modelling and Optimization (Z\u00fcrich 1991). Lect. Notes Control Inf. Sci., vol. 180, pp. 45\u201354. Springer, Berlin (1992)","DOI":"10.1007\/BFb0113271"},{"key":"422_CR24","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1080\/0025570X.1975.11976434","volume":"48","author":"GE Reis","year":"1975","unstructured":"Reis, G.E.: Dense packing of equal circles within a circle. Math. Mag. 48, 33\u201337 (1975)","journal-title":"Math. Mag."},{"key":"422_CR25","unstructured":"Specht, E.: Packomania (2015). http:\/\/www.packomania.com"},{"issue":"3","key":"422_CR26","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF03167582","volume":"21","author":"K Sugihara","year":"2004","unstructured":"Sugihara, K., Sawai, M., Sano, H., Kim, D.-S., Kim, D.: Disk packing for the estimation of the size of a wire bundle. Jpn. J. Ind. Appl. Math. 21(3), 259\u2013278 (2004)","journal-title":"Jpn. J. Ind. Appl. Math."},{"key":"422_CR27","unstructured":"Szab\u00f3, P.G., Mark\u00f3t, M.Cs., Csendes, T., Specht, E., Casado, L.G., Garc\u00eda, I.: New Approaches to Circle Packing in a Square. Springer Optimization and Its Applications, vol.\u00a06. Springer, New York (2007)"},{"issue":"2","key":"422_CR28","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1016\/S0377-2217(01)00241-7","volume":"141","author":"H Wang","year":"2002","unstructured":"Wang, H., Huang, W., Zhang, Q., Xu, D.: An improved algorithm for the packing of unequal circles within a larger containing circle. Eur. J. Oper. Res. 141(2), 440\u2013453 (2002)","journal-title":"Eur. J. Oper. Res."},{"key":"422_CR29","unstructured":"W\u00fcrtz, D., Monagan, M., Peikert, R.: The history of packing circles in a square. Maple Technical Newsletter, 35\u201342 (1994)"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00422-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-022-00422-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00422-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T20:03:59Z","timestamp":1672603439000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-022-00422-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,15]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["422"],"URL":"https:\/\/doi.org\/10.1007\/s00454-022-00422-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2022,9,15]]},"assertion":[{"value":"3 September 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 June 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 September 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}