Boundary Labeling: Models and Efficient Algorithms
for Rectangular Maps
Computational Geometry: Theory and Applications, 36 (3):
215--236 (2007)DOI: 10.1016/j.comgeo.2006.05.003
Zusammenfassung
In this paper, we present boundary labeling,
a new approach for labeling point sets with large
labels. We first place disjoint labels around an
axis-parallel rectangle that contains the point
sites. Then, we connect each label to its site such
that no two connections, so-called leaders,
intersect. Such an approach is common e.g.\ in
technical drawings and medical atlases, but so far
the problem has not been studied in the
literature. The new problem is interesting in that
it is a mixture of a label-placement and a
graph-drawing problem. We consider attaching
labels to one, two or all four sides of the
rectangle. We investigate rectilinear and
straight-line leaders. We present simple and
efficient algorithms that minimize the total length
of the leaders or, in the case of rectilinear
leaders, the total number of bends.
