2026-08-14T15:21:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16401 2024-03-06T10:57:23Z ddc:004 open_access

(Re)packing Equal Disks into Rectangle Fomin, Fedor V. Golovach, Petr A. Inamdar, Tanmay Zehavi, Meirav circle packing unit disks parameterized complexity fixed-parameter tractability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor V. Fomin and Petr A. Golovach and Tanmay Inamdar and Meirav Zehavi 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.60 urn:nbn:de:0030-drops-164011 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.60 eng https://creativecommons.org/licenses/by/4.0/legalcode