Boundary Labeling in Text Annotation

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.