(Re)packing Equal Disks into Rectangle.

Autor: Fomin FV; University of Bergen, Bergen, Norway., Golovach PA; University of Bergen, Bergen, Norway., Inamdar T; Indian Institute of Technology, Jodhpur, Jodhpur, India., Saurabh S; University of Bergen, Bergen, Norway.; Institute of Mathematical Sciences, Chennai, India., Zehavi M; Ben-Guiron University, Beer-Sheva, Israel.
Jazyk: angličtina
Zdroj: Discrete & computational geometry [Discrete Comput Geom] 2024; Vol. 72 (4), pp. 1596-1629. Date of Electronic Publication: 2024 Mar 12.
DOI: 10.1007/s00454-024-00633-1
Abstrakt: 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 .
(© The Author(s) 2024.)
Databáze: MEDLINE
Externí odkaz: