A new approximation algorithm for labeling points with circle pairs

摘要

We study the NP-hard problem of labeling points with maximum-radius circle pairs: given n point sites in the plane, find a placement for 2n interior-disjoint uniform circles, such that each site touches two circles and the circle radius is maximized. We present a new approximation algorithm for this problem that runs in O(n log n + n log 1/ε) time and O(n) space and achieves an approximation factor of (2 + 3~(1/2) + 2(4+3~(1/2))~(1/2)/(4 + 3~(1/2)) + ε (≈ 1.486 + ε), which improves the previous best bound of 1.491 +ε.