A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM
Marc Benkert, Joachim Gudmundsson, Christian Knauer, René van Oostrum, Alexander Wolff · International Journal of Computational Geometry & Applications · 2009
We consider the following packing problem. Let α be a fixed real in (0, 1]. We are given a bounding rectangle ρ and a set [Formula: see text] of n possibly intersecting unit disks whose centers lie in ρ. The task is to pack a set [Formula: see text] of m disjoint disks of radius α into ρ such that no disk in B intersects a disk in [Formula: see text], where m is the maximum number of unit disks that can be packed. In this paper we present a polynomial-time algorithm for α = 2/3. So far only the case of packing squares has been considered. For that case, Baur and Fekete have given a polynomial-time algorithm for α = 2/3 and have shown that the problem cannot be solved in polynomial time for any α > 13/14 unless [Formula: see text].