dc.contributor.author Fomin, Fedor dc.contributor.author Golovach, Petr dc.contributor.author Inamdar, Tanmay Nitin dc.contributor.author Zehavi, Meirav dc.date.accessioned 2023-01-10T11:57:52Z dc.date.available 2023-01-10T11:57:52Z dc.date.created 2022-11-04T12:29:36Z dc.date.issued 2022 dc.identifier.issn 1868-8969 dc.identifier.uri https://hdl.handle.net/11250/3042293 dc.description.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. en_US 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. dc.language.iso eng en_US dc.publisher Schloss Dagstuhl – Leibniz Center for Informatics en_US dc.rights Navngivelse 4.0 Internasjonal * dc.rights.uri http://creativecommons.org/licenses/by/4.0/deed.no * dc.title (Re)packing Equal Disks into Rectangle en_US dc.type Journal article en_US dc.type Peer reviewed en_US dc.description.version publishedVersion en_US dc.rights.holder Copyright 2022 the authors en_US dc.source.articlenumber 60 en_US cristin.ispublished true cristin.fulltext original cristin.qualitycode 1 dc.identifier.doi https://doi.org/10.4230/LIPIcs.ICALP.2022.60 dc.identifier.cristin 2069164 dc.source.journal Leibniz International Proceedings in Informatics en_US dc.source.pagenumber 60:1-60:17 en_US dc.relation.project Norges forskningsråd: 314528 en_US dc.identifier.citation Leibniz International Proceedings in Informatics. 2022, 229, 60:1-60:17. en_US dc.source.volume 229 en_US
﻿

This item appears in the following Collection(s)

Except where otherwise noted, this item's license is described as Navngivelse 4.0 Internasjonal