Abstract | ||
---|---|---|
In this paper, we consider a map labeling problem to maximize the number of independent labels in the plane. We first investigate the point labeling model that each label can be placed on a given set of anchors on a horizontal line. It is known that most of the map labeling decision models on a single line (horizontal or slope line) can be easily solved. However, the label number maximization models are more difficult (like 2SAT vs. MAX-2SAT). We present an O(n log Δ) time algorithm for the four position label model on a horizontal line based on dynamic programming and a particular analysis, where n is the number of the anchors and Δ is the maximum number of labels whose intersection is nonempty. As a contrast to Agarwal et al.'s result [Comput. Geom. Theory Appl. 11 (1998) 209-218] and Chan's result [Inform. Process. Letters 89(2004) 19-23] in which they provide (1 + 1/k)-factor PTAS algorithms that run in O(n log n + n2k-1) time and O(n log n + nΔk-1) time respectively for the fixed-height rectangle label placement model in the plane, we extend our method to improve their algorithms and present a (1 + 1/k)-factor PTAS algorithm that runs in O(n log n + kn log4 Δ + Δk-1) time using O(kΔ3 log4 Δ + kΔk-1) storage. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1007/978-3-540-73814-5_13 | FAW |
Keywords | Field | DocType |
horizontal line,n log,label number maximization model,fixed-height rectangle label placement,n log n,factor ptas algorithm,maximum number,independent label,position label model,single line,maximum independent set,decision models,dynamic programming algorithm,information processing | Dynamic programming,Combinatorics,GEOM,Rectangle,Time complexity,Map labeling,Horizontal line test,Maximization,Polynomial-time approximation scheme,Mathematics | Conference |
Volume | ISSN | ISBN |
4613 | 0302-9743 | 3-540-73813-4 |
Citations | PageRank | References |
2 | 0.41 | 18 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Kuen-Lin Yu | 1 | 2 | 0.41 |
Chung-shou Liao | 2 | 320 | 20.95 |
D.T. Lee | 3 | 627 | 78.14 |