A new bound for map labeling with uniform circle pairs

Given a planar point set, we wish to label the points with uniform circular labels such that each input point lies on them boundary of two labels, non e of the interiors of the labels intersect, and the size of the labels is m aximized. This problem is known as map-labeling with uniform circular pairs (MLUCP) and has been shown to be NP-hard. In this paper, we give an O(n lo g n) time, O(n) space algorithm that computes a labeling, such that the dia meter of the circular labels in an optimum solution is no more than (1 + ro ot 33)/4 approximate to 1.686 times the diameter of the labels computed by our algorithm. (C) 2002 Elsevier Science B.V. All rights reserved.