Fomin, Fedor V. ;
Golovach, Petr A. ;
Inamdar, Tanmay ;
Zehavi, Meirav
(Re)packing Equal Disks into Rectangle
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 NPhard 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 fixedparameter tractable parameterized by k and h.
BibTeX  Entry
@InProceedings{fomin_et_al:LIPIcs.ICALP.2022.60,
author = {Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Zehavi, Meirav},
title = {{(Re)packing Equal Disks into Rectangle}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {60:160:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16401},
URN = {urn:nbn:de:0030drops164011},
doi = {10.4230/LIPIcs.ICALP.2022.60},
annote = {Keywords: circle packing, unit disks, parameterized complexity, fixedparameter tractability}
}
28.06.2022
Keywords: 

circle packing, unit disks, parameterized complexity, fixedparameter tractability 
Seminar: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Issue date: 

2022 
Date of publication: 

28.06.2022 