Document Open Access Logo

(Re)packing Equal Disks into Rectangle

Authors Fedor V. Fomin , Petr A. Golovach , Tanmay Inamdar , Meirav Zehavi

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.60.pdf
  • Filesize: 0.86 MB
  • 17 pages

Document Identifiers

Author Details

Fedor V. Fomin
  • Department of Informatics, University of Bergen, Norway
Petr A. Golovach
  • Department of Informatics, University of Bergen, Norway
Tanmay Inamdar
  • Department of Informatics, University of Bergen, Norway
Meirav Zehavi
  • Ben-Gurion University of the Negev, Beer-Sheva, Israel

Funding

  • Fomin, Fedor V.: Supported by the Research Council of Norway via the project BWCA, grant no. 314528.
  • Golovach, Petr A.: Supported by the Research Council of Norway via the project BWCA, grant no. 314528.
  • Inamdar, Tanmay: Supported by the European Research Council (ERC) via grant LOPPRE, reference 819416.
  • Zehavi, Meirav: Supported by the Israel Science Foundation (ISF) grant no. 1176/18.

Cite As Get BibTex

Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, and Meirav Zehavi. (Re)packing Equal Disks into Rectangle. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 60:1-60:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.60

Abstract

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 n equal disks packed into a rectangle and integers k and h, we ask whether it is possible by changing positions of at most h disks to pack n+k disks. Thus the problem of packing equal disks is the special case of our problem with n = h = 0.
While the computational complexity of packing equal disks into a rectangle remains open, we prove that the repacking problem is NP-hard already for h = 0. Our main algorithmic contribution is an algorithm that solves the repacking problem in time (h+k)^𝒪(h+k)⋅|I|^𝒪(1), where |I| is the input size. That is, the problem is fixed-parameter tractable parameterized by k and h.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • circle packing
  • unit disks
  • parameterized complexity
  • fixed-parameter tractability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Mikkel Abrahamsen, Tillmann Miltzow, and Nadja Seiferth. Framework for er-completeness of two-dimensional packing problems. In 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 1014-1021. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00098.
  2. Pradeesha Ashok, Sudeshna Kolay, Syed Mohammad Meesum, and Saket Saurabh. Parameterized complexity of strip packing and minimum volume packing. Theor. Comput. Sci., 661:56-64, 2017. URL: https://doi.org/10.1016/j.tcs.2016.11.034.
  3. Brenda S. Baker. Approximation algorithms for np-complete problems on planar graphs. J. ACM, 41(1):153-180, 1994. URL: https://doi.org/10.1145/174644.174650.
  4. Nikhil Bansal and Arindam Khan. Improved approximation algorithm for two-dimensional bin packing. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 13-25. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.2.
  5. Saugata Basu, Richard Pollack, and Marie-Françoise Roy. Algorithms in Real Algebraic Geometry. Springer, Berlin, Heidelberg, 2009. Google Scholar
  6. Ignacio Castillo, Frank J Kampas, and János D Pintér. Solving circle packing problems by global optimization: numerical results and industrial applications. European Journal of Operational Research, 191(3):786-802, 2008. Google Scholar
  7. Henrik I. Christensen, Arindam Khan, Sebastian Pokutta, and Prasad Tetali. Approximation and online algorithms for multidimensional bin packing: A survey. Comput. Sci. Rev., 24:63-79, 2017. URL: https://doi.org/10.1016/j.cosrev.2016.12.001.
  8. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2006. Google Scholar
  9. Hallard T Croft, Kenneth Falconer, and Richard K Guy. Unsolved problems in geometry: unsolved problems in intuitive mathematics, volume 2. Springer Science & Business Media, 2012. Google Scholar
  10. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  11. Erik D. Demaine, Sándor P. Fekete, and Robert J. Lang. Circle packing for origami design is hard. CoRR, abs/1008.1224, 2010. URL: http://arxiv.org/abs/1008.1224.
  12. Sándor P. Fekete, Sebastian Morr, and Christian Scheffer. Split packing: Algorithms for packing circles with optimal worst-case density. Discret. Comput. Geom., 61(3):562-594, 2019. URL: https://doi.org/10.1007/s00454-018-0020-2.
  13. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization. Cambridge University Press, Cambridge, 2019. Theory of parameterized preprocessing. Google Scholar
  14. Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala, Sandy Heydrich, Arindam Khan, and Andreas Wiese. Approximating geometric knapsack via l-packings. ACM Trans. Algorithms, 17(4):33:1-33:67, 2021. URL: https://doi.org/10.1145/3473713.
  15. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  16. Michael Goldberg. The packing of equal circles in a square. Mathematics Magazine, 43(1):24-30, 1970. URL: https://doi.org/10.1080/0025570X.1970.11975991.
  17. Rolf Harren, Klaus Jansen, Lars Prädel, and Rob van Stee. A (5/3 + ε)-approximation for strip packing. Comput. Geom., 47(2):248-267, 2014. URL: https://doi.org/10.1016/j.comgeo.2013.08.008.
  18. Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM, 32(1):130-136, 1985. URL: https://doi.org/10.1145/2455.214106.
  19. Klaus Jansen and Malin Rau. Closing the gap for pseudo-polynomial strip packing. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 62:1-62:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.62.
  20. Johannes Kepler. Strena seu de nive sexangula. Frankfurt: Godefrid Tampach, 1611. Google Scholar
  21. Marco Locatelli and Ulrich Raber. Packing equal circles in a square: a deterministic global optimization approach. Discrete Applied Mathematics, 122(1-3):139-166, 2002. Google Scholar
  22. Costas D Maranas, Christodoulos A Floudas, and Panos M Pardalos. New results in the packing of equal circles in a square. Discrete Mathematics, 142(1-3):287-293, 1995. Google Scholar
  23. Moni Naor, Leonard J. Schulman, and Aravind Srinivasan. Splitters and near-optimal derandomization. In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 182-191, 1995. Google Scholar
  24. Kari J Nurmela et al. More optimal packings of equal circles in a square. Discrete & Computational Geometry, 22(3):439-457, 1999. Google Scholar
  25. Kari J Nurmela and Patric RJ Östergård. Packing up to 50 equal circles in a square. Discrete & Computational Geometry, 18(1):111-120, 1997. Google Scholar
  26. J Schaer. The densest packing of 9 circles in a square. Canadian Mathematical Bulletin, 8(3):273-277, 1965. Google Scholar
  27. E Specht. The best known packings of equal circles in a square (up to N= 10000), 2015. URL: http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html.
  28. Péter Gábor Szabó, Mihaly Csaba Markót, Tibor Csendes, Eckard Specht, Leocadio G Casado, and Inmaculada García. New approaches to circle packing in a square: with program codes, volume 6. Springer Science & Business Media, 2007. Google Scholar
  29. L Fejes Tóth. Lagerungen in der Ebene auf der Kugel und im Raum. Springer, 1953. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact