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. 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.
Users
Please
log in to take part in the discussion (add own reviews or comments).