%0 Journal Article %1 bgkow-ptaag-09 %A Benkert, Marc %A Gudmundsson, Joachim %A Knauer, Christian %A van Oostrum, René %A Wolff, Alexander %D 2009 %J International Journal of Computational Geometry and Applications %K %N 3 %P 267--288 %R 10.1142/S0218195909002952 %T A Polynomial-Time Approximation Algorithm for a Geometric Dispersion Problem %V 19 %X 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 $R$ of $n$ possibly intersecting unit disks whose centers lie in~$\rho$. The task is to pack a set $B$ of $m$ disjoint disks of radius $\alpha$ into $\rho$ such that no disk in $B$ intersects a disk in $\cal R$, 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 $\alpha=2/3$ and have shown that the problem cannot be solved in polynomial time for any $> 13/14$ unless $P=NP$.

@article{bgkow-ptaag-09, abstract = {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 that the problem cannot be solved in polynomial time for any $\alpha > 13/14$ unless ${\cal P}={\cal NP}$.}, added-at = {2023-12-14T15:35:57.000+0100}, author = {Benkert, Marc and Gudmundsson, Joachim and Knauer, Christian and van Oostrum, Ren{\'e} and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/20d7ff7eaa93ca6ab0d3b6b2cf2e4610b/admin}, doi = {10.1142/S0218195909002952}, interhash = {ed2b3dae1ddeaf6c99ad03d74dfa4804}, intrahash = {0d7ff7eaa93ca6ab0d3b6b2cf2e4610b}, journal = {International Journal of Computational Geometry and Applications}, keywords = {}, number = 3, pages = {267--288}, pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/bgkow-ptaag-09.pdf}, succeeds = {bgkmow-ptaag-06t}, timestamp = {2023-12-14T15:35:57.000+0100}, title = {A Polynomial-Time Approximation Algorithm for a Geometric Dispersion Problem}, volume = 19, year = 2009 }