Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/685
New algorithms for twolabel point labeling
Authors  Qin, Zhongping
Wolff, Alexander Xu, YinFeng Zhu, Binhai 


Issue Date  2000  
Summary  Given a label shape L and a set of n points in the plane, the twolabel pointlabeling problem consists of placing 2n nonintersecting translated copies of L of maximum size such that each point touches two unique copiesits labels. In this paper we give new and simple approximation algorithms for L an axisparallel square or a circle. For squares we improve the best previously known approximation factor from 1/3 to 1/2. For circles the improvement from 1/2 to roughly 0.5125 is less significant, but the fact that 1/2 is not best possible is interesting in its own right. For the decision version of the latter problem we have an NPhardness proof that also shows that it is NPhard to approximate the label size beyond a factor of ≈ 0.7321. We keep the O(nlogn) time and O(n) space bounds of the previous algorithms. The algorithm we propose for the twosquare labeling problem actually solves a different problem. It labels points with rectangles of heightwidth ratio 2 of maximum size in one of four positions. It is the first pointlabeling algorithm that combines the following properties. It allows more than two label positions and solves the size maximization problem optimally in polynomial time. This algorithm also improves the approximation factor of the only known algorithm for Knuth and Raghunathan's Metafont labeling problem from 1/3 to 1/2.  
Subjects  
Language  English 

Format  Technical report  
Access 
Files in this item:
