Abstract | ||
---|---|---|
Abstract In this paper, we consider a map labeling problem where the points to be labeled are restricted on a line. It is known that the 1d-4P and the 1d-4S unit-square label placement problem and the Slope-4P unit-square label placement problem can both be solved in linear time and the Slope-4S unit-square label placement problem can be solved in quadratic time in [7]. We extend the result to the following label placement problem: Slope-4P fixed-height (width) label placement problem and elastic labels and present a linear time algorithm for it provided that the input points are given sorted. We further show that if the points are not sorted, the label placement problems have a lower bound of ›(nlogn), where n is the input size, under the algebraic computation tree model. Optimization versions of these point labeling problems are also considered. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1142/S0218195905001695 | Int. J. Comput. Geometry Appl. |
DocType | Volume | Issue |
Journal | 15 | 3 |
Citations | PageRank | References |
3 | 0.43 | 13 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yu-shin Chen | 1 | 14 | 1.59 |
D.T. Lee | 2 | 627 | 78.14 |
Chung-shou Liao | 3 | 320 | 20.95 |