A polynomial-time approximation algorithm for a geometric dispersion problem

We consider the problem of placing a maximal number of disks in a rectangular region containing obstacles such that no two disks intersect. Let $\alpha$ be a fixed real in $(0,1]$. We are given a bounding rectangle $P$ and a set $\cal{R}$ of possibly intersecting unit disks whose centers lie in~$P$. The task is to pack a set $\cal{B}$ of $m$ disjoint disks of radius $\alpha$ into $P$ such that no disk in $\cal{B}$ intersects a disk in $\cal{R}$, where $m$ is the maximum number of \emph{unit} disks that can be packed. Baur and Fekete showed that the problem cannot be solved in polynomial time for any $\alpha <1$, unless ${\cal P}={\cal NP}$. In this paper we present a polynomial time algorithm for $\alpha = 2/3$.