Joachim Gudmundsson
We consider the following packing problem. Let $\alpha$ be a fixed real in $(0,1]$. We are given a bounding rectangle $\rho$ and a set $\cal{R}$ of $n$ possibly intersecting unit disks whose centers lie in~$\rho$. The task is to pack a set $\cal{B}$ of $m$ disjoint disks of radius $\alpha$ into $\rho$ 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. In this paper we present a polynomial-time algorithm for $\alpha = 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 $\alpha=2/3$ and have shown the problem cannot be solved in polynomial time for any $\alpha > 13/14$ unless ${\cal P}={\cal NP}$.
This is joint work with Marc Benkert, Christian Knauer, Rene van Oostrum and Alexander Wolff