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.
%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 Voronoi_diagram approximation_algorithm cartography multi-label_point_labeling myown
%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 = {2024-04-29T21:12:31.000+0200},
author = {Wolff, Alexander and Thon, Michael and Xu, Yinfeng},
biburl = {https://www.bibsonomy.org/bibtex/23d120c25bc1bb52707162f698be22d0e/awolff},
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 = {Voronoi_diagram approximation_algorithm cartography multi-label_point_labeling myown},
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 = {2024-04-29T21:12:31.000+0200},
title = {A Simple Factor-2/3 Approximation Algorithm for
Two-Circle Point Labeling},
volume = 12,
year = 2002
}