Abstract
Placing labels that contain text or images is a common task in
information visualization. Labels convey information about objects in
graphical displays like graphs, networks, diagrams, or cartographic
maps. Typically, each object (or feature) that has to be
labeled allows a number of positions where the corresponding label can
be placed. However, each of these label candidates could intersect
with label candidates of other features. This gives rise to the
following combinatorial problem, the general label-placement
decision problem. Given a set of features, each with a set of
label candidates, can we assign each feature a label from its
candidate set such that no two labels intersect? In other words, is
there a complete labeling for the set of features?
Unfortunately, one cannot expect to find an efficient method for
answering this question. Therefore most previous work has focused on
developing heuristics and approximation algorithms for various
optimization problems related to label placement, such as finding a
placement for a subset of the features of maximum cardinality that has
a complete labeling. This problem is referred to as the
label-number maximization problem.
In this thesis we approach label placement from two sides. On the one
hand we develop a general framework for label-placement problems.
This framework extends the classical constraint-satisfaction framework
such that the label-number maximization problem can be formulated and
algorithms can be developed that reduce the size of the search space
for an optimal solution considerably. We give such an algorithm and a
simple, but very effective heuristic based on this algorithm.
On the other hand we investigate special cases of the label-placement
problem, which is generally divided into point, line, and area
labeling. First we consider the point-labeling problem. We apply our
framework to labeling points with axis-parallel rectangles, which can,
for example, represent the bounding boxes of textual labels. We allow
the classical four label positions per point, namely those where a
corner of the rectangle coincides with the point. We compare our
method to five other point-labeling algorithms experimentally. Then we
investigate point labeling with an infinite number of label candidates
per point. We show that it is NP-hard to decide whether a set of
points can be labeled with unit squares or with unit disks if we
require that each label touches its point. Nevertheless we give
efficient approximation algorithms for optimization versions of both
problems. More specifically we give a polynomial-time approximation
scheme for maximizing the number of axis-parallel rectangular labels
of common height, while we show that one cannot expect to find such a
scheme for maximizing the size of uniform circular labels.
For labeling polygonal chains like rivers or railway lines on maps, we
study the cartographers' requirements and put them into two
categories; hard and soft constraints. Then we give an efficient
algorithm that guarantees to satisfy all hard constraints. In
addition we show how to optimize the soft constraints. The method we
suggest is the first that simultaneously fulfills both of the
following two requirements: it allows curved labels and its runtime is
at most quadratic in the number of points on the given polyline.
Apart from analyzing asymptotical runtime behavior and storage
requirements of our algorithms, we implemented most of them and
studied their performance on synthetic as well as real-world data.
The last chapter of this thesis is devoted to generic programming, a
method for abstracting from concrete data representation, that we
found very helpful for keeping our geometric algorithms flexible. |
