1. LABELING POINTS ON A SINGLE LINE.
- Author
-
Yu-Shin Chen, Lee, D. T., and Chung-Shou Liao
- Subjects
- *
ALGORITHMS , *ALGEBRA , *DECISION trees , *CHARTS, diagrams, etc. , *DECISION making , *MATHEMATICAL models , *GRAPH labelings , *GRAPH theory - 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 Ref. [8]. We extend the result to the following label placement problem: Slope-4P fixed-height (width) label or elastic label placement problem 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 Ω(n log n), where n is the input size, under the algebraic computation tree model. Optimization versions of these point labeling problems are also considered. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF