Labeling Points on a Single Line
Resource
International Journal of Computational Geometry & Applications, vol.15, 2005
Journal
International Journal of Computational Geometry & Applications
Pages
261-277
Date Issued
2005
Date
2005
Author(s)
Y. S. Chen
D. T. Lee
C. S Liao
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 ld-4P and the ld-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. © World Scientific Publishing Company.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
910.pdf
Size
186.95 KB
Format
Adobe PDF
Checksum
(MD5):35e52af81eb2ce9308e2ddeffb3a57db