TY - JOUR
T1 - Boundary labeling in text annotation
AU - Lin, Chun-Cheng
AU - Wu, Hsiang Yun
AU - Yen, Hsu Chun
PY - 2009/11/19
Y1 - 2009/11/19
N2 - The text annotation system of a word processor software provides the user the function of memorandums in editing a document. In the visualization interface of the annotation system, each marked word is connected to a text comment label on the right side of the document by a polygonal line. Such a visualization interface can be viewed as a one-side boundary labeling, in which each point site is uniquely connected to a label placed on the right side of an enclosing rectangle by a leader, which may be a rectilinear or straight line segment. In the literature, there have existed some applications and some theoretical results for the boundary labeling. In this paper, we investigate the boundary labeling from the application on the annotation system. For this kind of labeling, if the number of labels on the right side is large, the leaders may be drawn too densely to be recognized easily. Therefore, in this paper, we propose a polynomial time algorithm for the so-called 1.5-side boundary labeling for the annotation system, in which, in addition to being connected to the right side directly, leaders can be routed to the left side temporarily and then finally to the right side. In addition, we investigate a problem for two-side boundary labeling (for the annotation system) that was not discussed previously. We show the problem to be NP-complete, and then proposed a heuristic based on the genetic algorithm to solve it. The experimental results reveal that our approach performs well.
AB - The text annotation system of a word processor software provides the user the function of memorandums in editing a document. In the visualization interface of the annotation system, each marked word is connected to a text comment label on the right side of the document by a polygonal line. Such a visualization interface can be viewed as a one-side boundary labeling, in which each point site is uniquely connected to a label placed on the right side of an enclosing rectangle by a leader, which may be a rectilinear or straight line segment. In the literature, there have existed some applications and some theoretical results for the boundary labeling. In this paper, we investigate the boundary labeling from the application on the annotation system. For this kind of labeling, if the number of labels on the right side is large, the leaders may be drawn too densely to be recognized easily. Therefore, in this paper, we propose a polynomial time algorithm for the so-called 1.5-side boundary labeling for the annotation system, in which, in addition to being connected to the right side directly, leaders can be routed to the left side temporarily and then finally to the right side. In addition, we investigate a problem for two-side boundary labeling (for the annotation system) that was not discussed previously. We show the problem to be NP-complete, and then proposed a heuristic based on the genetic algorithm to solve it. The experimental results reveal that our approach performs well.
UR - http://www.scopus.com/inward/record.url?scp=70449491642&partnerID=8YFLogxK
U2 - 10.1109/IV.2009.84
DO - 10.1109/IV.2009.84
M3 - Conference article
AN - SCOPUS:70449491642
SN - 1093-9547
SP - 110
EP - 115
JO - Proceedings of the International Conference on Information Visualisation
JF - Proceedings of the International Conference on Information Visualisation
M1 - 5190766
T2 - 2009 13th International Conference on Information Visualisation, IV 2009
Y2 - 15 July 2009 through 17 July 2009
ER -