TY - GEN

T1 - New algorithms for two-label point labeling

AU - Qin, Z.

AU - Wolff, A.

AU - Xu, Y.F.

AU - Zhu, B.

PY - 2000

Y1 - 2000

N2 - Given a label shape L and a set of n points in the plane, the 2-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 ˜ 0.513 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.732. As their predecessors, our algorithms take O(n log n) time and O(n) space.

AB - Given a label shape L and a set of n points in the plane, the 2-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 ˜ 0.513 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.732. As their predecessors, our algorithms take O(n log n) time and O(n) space.

U2 - 10.1007/3-540-45253-2_34

DO - 10.1007/3-540-45253-2_34

M3 - Conference contribution

SN - 3-540-41004-X

T3 - Lecture Notes in Computer Science

SP - 368

EP - 379

BT - Algorithms - ESA 2000 (Proceedings 8th Annual European Symposium, Saarbrücken, Germany, September 5-8, 2000)

A2 - Paterson, M.

PB - Springer

CY - Berlin

ER -