Improved Algorithms for Length-Minimal One-Sided Boundary Labeling
Marc Benkert, Martin Nöllenburg · European Workshop on Computational Geometry · 2007
We present algorithms for labeling n points that are contained in a rectangle R by labels that lie on one side of R. The points are connected to their labels by non-intersecting curves (leaders) that each have at most one bend. We consider two types of curves: rectilinear leaders, called po-leaders, and leaders that consist of a horizontal and a diagonal segment, called do-leaders. To obtain a good readability of the labeling we minimize the total leader length. For the po-leaders we give an O(n log n) and for do-leaders an O(n)-time algorithm. This type of labeling has applications for geographic maps or illustrations in medical atlases in which the labels should not be inserted directly because labels would obscure important information or if points lie too dense.