%0 Journal Article %1 wtx-sf23a-02 %A Wolff, Alexander %A Thon, Michael %A Xu, Yinfeng %D 2002 %J International Journal of Computational Geometry and Applications %K %N 4 %P 269--281 %R 10.1142/S0218195902000888 %T A Simple Factor-2/3 Approximation Algorithm for Two-Circle Point Labeling %V 12 %X Given a set $P$ of $n$ points in the plane, the two-circle point-labeling problem consists of placing $2n$ uniform, non-intersecting, maximum-size open circles such that each point touches exactly two circles. It is known that this problem is NP-hard to approximate. In this paper we give a simple algorithm that improves the best previously known approximation factor from $4/(1+33) 0.5931$ to 2/3. The main steps of our algorithm are as follows. We first compute the Voronoi diagram, then label each point optimally within its cell, compute the smallest label diameter over all points and finally shrink all labels to this size. We keep the $O(n n)$ time and $O(n)$ space bounds of the previously best algorithm.

@article{wtx-sf23a-02, abstract = {Given a set $P$ of $n$ points in the plane, the two-circle point-labeling problem consists of placing $2n$ uniform, non-intersecting, maximum-size open circles such that each point touches exactly two circles. \par It is known that this problem is NP-hard to approximate. In this paper we give a simple algorithm that improves the best previously known approximation factor from $4/(1+\sqrt{33}) \approx 0.5931$ to 2/3. The main steps of our algorithm are as follows. We first compute the Voronoi diagram, then label each point \emph{optimally} within its cell, compute the smallest label diameter over all points and finally shrink all labels to this size. We keep the $O(n \log n)$ time and $O(n)$ space bounds of the previously best algorithm.}, added-at = {2023-12-13T10:33:27.000+0100}, author = {Wolff, Alexander and Thon, Michael and Xu, Yinfeng}, biburl = {https://www.bibsonomy.org/bibtex/23d120c25bc1bb52707162f698be22d0e/admin}, cites = {af-aesam-84, agss-ltacv-89, a-vdsfg-91, bckm-ap2cc-98, c-cgitf-99, cms-esapf-95, df-esdmn-89, dmmmz-mlg-97, dmm-pslsp-00, fw-ppalm-91, h-aanpa-82, ksy-lrmsl-99, kt-mlpp-98, m-ctcc-80, ocon-nlaic-82, qwxz-na2lp-00, sw-lpc-01, ksw-plsl-99, ws-mlb-96, wtx-blb2c-00, ww-pmla-97, z-sl01i-90, zp-eaa2l-01, ZZZ}, doi = {10.1142/S0218195902000888}, interhash = {d88a7e10d82ab947df54fc0ed607a23a}, intrahash = {3d120c25bc1bb52707162f698be22d0e}, journal = {International Journal of Computational Geometry and Applications}, keywords = {}, number = 4, pages = {269--281}, pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/wtx-sf23a-02.pdf}, succeeds = {wtx-blb2c-00}, timestamp = {2023-12-13T10:33:27.000+0100}, title = {A Simple Factor-2/3 Approximation Algorithm for Two-Circle Point Labeling}, volume = 12, year = 2002 }