Show simple item record

dc.contributor.authorFomin, Fedor
dc.contributor.authorGolovach, Petr
dc.contributor.authorInamdar, Tanmay Nitin
dc.contributor.authorZehavi, Meirav
dc.description.abstractThe 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.en_US
dc.publisherSchloss Dagstuhl – Leibniz Center for Informaticsen_US
dc.rightsNavngivelse 4.0 Internasjonal*
dc.title(Re)packing Equal Disks into Rectangleen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.rights.holderCopyright 2022 the authorsen_US
dc.source.journalLeibniz International Proceedings in Informaticsen_US
dc.relation.projectNorges forskningsråd: 314528en_US
dc.identifier.citationLeibniz International Proceedings in Informatics. 2022, 229, 60:1-60:17.en_US

Files in this item


This item appears in the following Collection(s)

Show simple item record

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