A new approximation algorithm for labeling points with circle pairs

作者：Jiang MH^*

来源：Information Processing Letters, 2006, 99(4): 125-129.

DOI：10.1016/j.ipl.2006.04.006

• computational geometry
• approximation algorithm
• map labeling
• circle packing

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 epsilon\1) time and O(n) space and achieves an approximation factor of (2 + root 3 + 2 root 4 + root 3)/(4 + root 3) + epsilon (approximate to 1.486 + epsilon), which improves the previous best bound of 1.491 + epsilon.

• 出版日期2006-8-31