@inproceedings{15ccbb6399ad464e96d4db96e31573f8,
title = "A better lower bound for two-circle point labeling",
abstract = "Given a set P of n points in the plane, the two-circle point-labeling problem consists of placing 2n uniform, non-intersecting, max-mum-size open circles such that each point touches exactly two circles. It is known that it is NP-hard to approximate the label size beyond a factor of ≈ 0:7321. In this paper we improve the best previously known approximation factor from ≈ 0:51 to 2/3. We keep the O(n log n) time and O(n) space bounds of the previous algorithm. As in the previous algorithm we label each point within its Voronoi cell. Unlike that algorithm we explicitely compute the Voronoi diagram, label each point optimally within its cell, compute the smallest label diameter over all points and finally shrink all labels to this size.",
author = "Alexander Wolff and Michael Thon and Yinfeng Xu",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2000.; 11th Annual International Symposium on Algorithms and Computation, ISAAC 2000 ; Conference date: 18-12-2000 Through 20-12-2000",
year = "2000",
doi = "10.1007/3-540-40996-3\_36",
language = "英语",
isbn = "3540412557",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "422--431",
editor = "D.T. Lee and Shang-Hua Teng and Shang-Hua Teng",
booktitle = "Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings",
}