Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/685

New algorithms for two-label point labeling

Authors Qin, Zhongping
Wolff, Alexander
Xu, Yin-Feng
Zhu, Binhai
Issue Date 2000
Summary Given a label shape L and a set of n points in the plane, the two-label point-labeling problem consists of placing 2n non-intersecting translated copies of L of maximum size such that each point touches two unique copies-its labels. In this paper we give new and simple approximation algorithms for L an axis-parallel 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 NP-hardness proof that also shows that it is NP-hard 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 two-square labeling problem actually solves a different problem. It labels points with rectangles of height-width ratio 2 of maximum size in one of four positions. It is the first point-labeling 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:
File Description Size Format
200006.pdf 235591 B Adobe PDF