(Re)packing Equal Disks into Rectangle

Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Meirav Zehavi

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

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)O(h+k) · |I|O(1), where |I| is the input size. That is, the problem is fixed-parameter tractable parameterized by k and h.

שפה מקוריתאנגלית אמריקאית
כותר פרסום המארח49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
עורכיםMikolaj Bojanczyk, Emanuela Merelli, David P. Woodruff
מקום הפרסוםDagstuhl, German
מוציא לאורSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
עמודים60:1-60:17
מספר עמודים17
כרך229
מסת"ב (אלקטרוני)9783959772358
מסת"ב (מודפס)978-3-95977-235-8
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 28 יוני 2022
אירוע49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 - Paris, צרפת
משך הזמן: 4 יולי 20228 יולי 2022

סדרות פרסומים

שםLeibniz International Proceedings in Informatics, LIPIcs
כרך229

כנס

כנס49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
מדינה/אזורצרפת
עירParis
תקופה4/07/228/07/22

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום '(Re)packing Equal Disks into Rectangle'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי