Please use this identifier to cite or link to this item:
標題: Labeling Points on a Single Line
作者: Y.S.Chen
關鍵字: Algorithm;algebraic decision tree;label optimization;lower bound;map labeling;uniform gap problem Read More:
Project: International Journal of Computational Geometry and Applications, Volume�15, Issue�3, Page(s) �261-277.
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 unit-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 Ω(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
DOI: 10.1142/S0218195905001695
Appears in Collections:資訊科學與工程學系所

Show full item record

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.