(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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 28 يونيو 2022
الحدث49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 - Paris, فرنسا
المدة: ٤ يوليو ٢٠٢٢٨ يوليو ٢٠٢٢

سلسلة المنشورات

الاسمLeibniz International Proceedings in Informatics, LIPIcs
مستوى الصوت229

!!Conference

!!Conference49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
الدولة/الإقليمفرنسا
المدينةParis
المدة٤/٠٧/٢٢٨/٠٧/٢٢

All Science Journal Classification (ASJC) codes

  • !!Software

بصمة

أدرس بدقة موضوعات البحث “(Re)packing Equal Disks into Rectangle'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا