When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.60
URN: urn:nbn:de:0030-drops-164011
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16401/
 Go to the corresponding LIPIcs Volume Portal

(Re)packing Equal Disks into Rectangle

 pdf-format:

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.

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:1--60:17},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-235-8},
ISSN =	{1868-8969},
year =	{2022},
volume =	{229},
editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},