|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE TCSC Research Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/685
|
| Title: | New algorithms for two-label point labeling |
| Authors: | Qin, Zhongping
Wolff, Alexander
Xu, Yin-Feng
Zhu, Binhai |
| Keywords: | Algorithms
Map labeling
NP-hardness |
| Issue Date: | 2000 |
| Series/Report no.: | HKUST Theoretical Computer Science Center Research Report ; HKUST-TCSC-2000-06 |
| Abstract: | 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. |
| URI: | http://hdl.handle.net/1783.1/685 |
| Appears in Collections: | CSE TCSC Research Reports
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| 200006.pdf | | 230Kb | Adobe PDF | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
