{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:17Z","timestamp":1771036337462,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["819416"],"award-info":[{"award-number":["819416"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005416","name":"Norges Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["314528"],"award-info":[{"award-number":["314528"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1176\/18"],"award-info":[{"award-number":["1176\/18"]}],"id":[{"id":"10.13039\/501100003977","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":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The problem of packing of equal disks (or circles) into a rectangle is a fundamental geometric problem. (By a packing here we mean an arrangement of disks in a rectangle without overlapping.) We consider the following algorithmic generalization of the equal disk packing problem. In this problem, for a given packing of equal disks into a rectangle, the question is whether by changing positions of a small number of disks, we can allocate space for packing more disks. More formally, in the repacking problem, for a given set of <jats:italic>n<\/jats:italic> equal disks packed into a rectangle and integers <jats:italic>k<\/jats:italic> and <jats:italic>h<\/jats:italic>, we ask whether it is possible by changing positions of at most <jats:italic>h<\/jats:italic> disks to pack <jats:inline-formula><jats:alternatives><jats:tex-math>$$n+k$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> disks. Thus the problem of packing equal disks is the special case of our problem with <jats:inline-formula><jats:alternatives><jats:tex-math>$$n=h=0$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>h<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>0<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. While the computational complexity of packing equal disks into a rectangle remains open, we prove that the repacking problem is NP-hard already for <jats:inline-formula><jats:alternatives><jats:tex-math>$$h=0$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>h<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>0<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Our main algorithmic contribution is an algorithm that solves the repacking problem in time <jats:inline-formula><jats:alternatives><jats:tex-math>$$(h+k)^{\\mathcal {O}(h+k)}\\cdot |I|^{\\mathcal {O}(1)}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msup>\n                      <mml:mrow>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>h<\/mml:mi>\n                        <mml:mo>+<\/mml:mo>\n                        <mml:mi>k<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                      <mml:mrow>\n                        <mml:mi>O<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>h<\/mml:mi>\n                        <mml:mo>+<\/mml:mo>\n                        <mml:mi>k<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>\u00b7<\/mml:mo>\n                    <mml:msup>\n                      <mml:mrow>\n                        <mml:mo>|<\/mml:mo>\n                        <mml:mi>I<\/mml:mi>\n                        <mml:mo>|<\/mml:mo>\n                      <\/mml:mrow>\n                      <mml:mrow>\n                        <mml:mi>O<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where |<jats:italic>I<\/jats:italic>| is the input size. That is, the problem is fixed-parameter tractable parameterized by <jats:italic>k<\/jats:italic> and <jats:italic>h<\/jats:italic>.<\/jats:p>","DOI":"10.1007\/s00454-024-00633-1","type":"journal-article","created":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T21:22:41Z","timestamp":1710278561000},"page":"1596-1629","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["(Re)packing Equal Disks into Rectangle"],"prefix":"10.1007","volume":"72","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tanmay","family":"Inamdar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,3,12]]},"reference":[{"key":"633_CR1","doi-asserted-by":"crossref","unstructured":"Abrahamsen, M., Miltzow, T., Seiferth, N.: Framework for er-completeness of two-dimensional packing problems. In: 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 1014\u20131021. IEEE (2020)","DOI":"10.1109\/FOCS46700.2020.00098"},{"issue":"4","key":"633_CR2","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"633_CR3","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.tcs.2016.11.034","volume":"661","author":"P Ashok","year":"2017","unstructured":"Ashok, P., Kolay, S., Meesum, S.M., Saurabh, S.: Parameterized complexity of strip packing and minimum volume packing. Theor. Comput. Sci. 661, 56\u201364 (2017)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"633_CR4","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for np-complete problems on planar graphs. J. ACM 41(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"633_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N., Khan, A.: Improved approximation algorithm for two-dimensional bin packing. In: Chekuri, C. (ed.) Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5\u20137, 2014, pp. 13\u201325. SIAM (2014)","DOI":"10.1137\/1.9781611973402.2"},{"key":"633_CR6","volume-title":"Algorithms in Real Algebraic Geometry","author":"S Basu","year":"2009","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Springer, Berlin (2009)"},{"issue":"3","key":"633_CR7","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":"633_CR8","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.cosrev.2016.12.001","volume":"24","author":"HI Christensen","year":"2017","unstructured":"Christensen, H.I., Khan, A., Pokutta, S., Tetali, P.: Approximation and online algorithms for multidimensional bin packing: a survey. Comput. Sci. Rev. 24, 63\u201379 (2017)","journal-title":"Comput. Sci. Rev."},{"key":"633_CR9","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, New York (2009)","edition":"3"},{"key":"633_CR10","volume-title":"Unsolved Problems in Geometry: Unsolved Problems in Intuitive Mathematics","author":"HT Croft","year":"2012","unstructured":"Croft, H.T., Falconer, K., Guy, R.K.: Unsolved Problems in Geometry: Unsolved Problems in Intuitive Mathematics, vol. 2. Springer, Berlin (2012)"},{"key":"633_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"633_CR12","unstructured":"Demaine, E.D., Fekete, S.P., Lang, R.J.: Circle packing for origami design is hard. CoRR https:\/\/arxiv.org\/abs\/1008.1224 (2010)"},{"key":"633_CR13","volume-title":"Graph Theory. Graduate Texts in Mathematics","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Berlin (2012)","edition":"4"},{"issue":"1","key":"633_CR14","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s00454-022-00422-8","volume":"69","author":"SP Fekete","year":"2023","unstructured":"Fekete, S.P., Keldenich, P., Scheffer, C.: Packing disks into disks with optimal worst-case density. Discrete Comput. Geom. 69(1), 51\u201390 (2023)","journal-title":"Discrete Comput. Geom."},{"key":"633_CR15","unstructured":"Fomin, F.V., Golovach, P.A., Inamdar, T., Zehavi, M.: (re)packing equal disks into rectangle. In: Bojanczyk, M., Merelli, E., Woodruff, D.P. (eds.) 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France. LIPIcs, vol. 229, pp. 60\u201316017. Schloss Dagstuhl, Leibniz (2022)"},{"key":"633_CR16","first-page":"515","volume-title":"Kernelization. Theory of Parameterized Preprocessing","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization. Theory of Parameterized Preprocessing, p. 515. Cambridge University Press, Cambridge (2019)"},{"issue":"4","key":"633_CR17","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/3473713","volume":"17","author":"W G\u00e1lvez","year":"2021","unstructured":"G\u00e1lvez, W., Grandoni, F., Ingala, S., Heydrich, S., Khan, A., Wiese, A.: Approximating geometric knapsack via l-packings. ACM Trans. Algorithms 17(4), 33\u201313367 (2021)","journal-title":"ACM Trans. Algorithms"},{"key":"633_CR18","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"issue":"1","key":"633_CR19","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1080\/0025570X.1970.11975991","volume":"43","author":"M Goldberg","year":"1970","unstructured":"Goldberg, M.: The packing of equal circles in a square. Math. Mag. 43(1), 24\u201330 (1970)","journal-title":"Math. Mag."},{"issue":"2","key":"633_CR20","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1016\/j.comgeo.2013.08.008","volume":"47","author":"R Harren","year":"2014","unstructured":"Harren, R., Jansen, K., Pr\u00e4del, L., van Stee, R.: A (5\/3 + $$\\epsilon $$)-approximation for strip packing. Comput. Geom. 47(2), 248\u2013267 (2014)","journal-title":"Comput. Geom."},{"issue":"1","key":"633_CR21","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32(1), 130\u2013136 (1985)","journal-title":"J. ACM"},{"key":"633_CR22","unstructured":"Jansen, K., Rau, M.: Closing the gap for pseudo-polynomial strip packing. In: Bender, M.A., Svensson, O., Herman, G. (eds.) 27th Annual European Symposium on Algorithms, ESA 2019, September 9\u201311, 2019, Munich\/Garching, Germany. LIPIcs, vol. 144, pp. 62\u201316214. Schloss Dagstuhl, Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"633_CR23","volume-title":"Strena Seu de Nive Sexangula","author":"J Kepler","year":"1611","unstructured":"Kepler, J.: Strena Seu de Nive Sexangula. Godefrid Tampach, Frankfurt (1611)"},{"key":"633_CR24","doi-asserted-by":"crossref","unstructured":"Litvinchev, I.S., Infante, L., Espinosa, E.L.O.: Approximate circle packing in a rectangular container: Integer programming formulations and valid inequalities. In: Gonz\u00e1lez-Ram\u00edrez, R.G., Schulte, F., Vo\u00df, S., D\u00edaz, J.A.C. (eds.) Computational Logistics - 5th International Conference, ICCL 2014, Valparaiso, Chile, September 24-26, 2014. Proceedings. Lecture Notes in Computer Science, vol. 8760, pp. 47\u201360. Springer, Berlin (2014)","DOI":"10.1007\/978-3-319-11421-7_4"},{"issue":"1\u20133","key":"633_CR25","first-page":"69","volume":"81","author":"Y Liu","year":"1998","unstructured":"Liu, Y., Morgana, A., Simeone, B.: A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid. Discrete Appl. Math. 81(1\u20133), 69\u201391 (1998)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"633_CR26","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0166-218X(01)00359-6","volume":"122","author":"M Locatelli","year":"2002","unstructured":"Locatelli, M., Raber, U.: Packing equal circles in a square: a deterministic global optimization approach. Discrete Appl. Math. 122(1\u20133), 139\u2013166 (2002)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"633_CR27","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0012-365X(93)E0230-2","volume":"142","author":"CD Maranas","year":"1995","unstructured":"Maranas, C.D., Floudas, C.A., Pardalos, P.M.: New results in the packing of equal circles in a square. Discrete Math. 142(1\u20133), 287\u2013293 (1995)","journal-title":"Discrete Math."},{"issue":"1","key":"633_CR28","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1006\/jctb.2000.2026","volume":"82","author":"B Mohar","year":"2001","unstructured":"Mohar, B.: Face covers and the genus problem for apex graphs. J. Comb. Theory Ser. B 82(1), 102\u2013117 (2001)","journal-title":"J. Comb. Theory Ser. B"},{"key":"633_CR29","doi-asserted-by":"crossref","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23\u201325 October 1995, pp. 182\u2013191. IEEE Computer Society (1995)","DOI":"10.1109\/SFCS.1995.492475"},{"issue":"1","key":"633_CR30","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/PL00009306","volume":"18","author":"KJ Nurmela","year":"1997","unstructured":"Nurmela, K.J., \u00d6sterg\u00e5rd, P.R.J.: Packing up to 50 equal circles in a square. Discrete Comput. Geom. 18(1), 111\u2013120 (1997)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"633_CR31","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/PL00009472","volume":"22","author":"KJ Nurmela","year":"1999","unstructured":"Nurmela, K.J., \u00d6sterg\u00e5rd, P.R.J.: More optimal packings of equal circles in a square. Discrete Comput. Geom. 22(3), 439\u2013457 (1999)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"633_CR32","doi-asserted-by":"publisher","first-page":"273","DOI":"10.4153\/CMB-1965-018-9","volume":"8","author":"J Schaer","year":"1965","unstructured":"Schaer, J.: The densest packing of 9 circles in a square. Can. Math. Bull. 8(3), 273\u2013277 (1965)","journal-title":"Can. Math. Bull."},{"key":"633_CR33","unstructured":"Specht, E.: The best known packings of equal circles in a square (up to N= 10000). English (2015). http:\/\/hydra.nat.uni-magdeburg.de\/packing\/csq\/csq.html"},{"key":"633_CR34","volume-title":"New Approaches to Circle Packing in a Square - With Program Codes. Optimization and Its Applications","author":"PG Szab\u00f3","year":"2007","unstructured":"Szab\u00f3, P.G., Mark\u00f3t, M.C., Csendes, T., Specht, E., Casado, L.G., Garc\u00eda, I.: New Approaches to Circle Packing in a Square - With Program Codes. Optimization and Its Applications, vol. 6. Springer, Berlin (2007)"},{"key":"633_CR35","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-01206-2","volume-title":"Lagerungen in der Ebene Auf der Kugel und Im Raum","author":"LF T\u00f3th","year":"1953","unstructured":"T\u00f3th, L.F.: Lagerungen in der Ebene Auf der Kugel und Im Raum. Springer, Berlin (1953)"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00633-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-024-00633-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00633-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,16]],"date-time":"2024-11-16T22:02:28Z","timestamp":1731794548000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-024-00633-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["633"],"URL":"https:\/\/doi.org\/10.1007\/s00454-024-00633-1","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]},"assertion":[{"value":"29 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 January 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 January 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 March 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}