Automated Label Placement in Theory and Practice

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.

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.

Bei der Visualisierung von Information auf Landkarten, in Graphen oder Diagrammen spielt die Beschriftung von Gestaltungselementen wie Punkten, Linienzügen oder Kanten eine große Rolle. So schätzt man, dass bei der manuellen Erstellung einer Landkarte ungefähr die Hälfte der Zeit für die Beschriftung benötigt wird. Dieser Umstand erklärt das Interesse daran, den Prozess des Beschriftens möglichst weitgehend zu automatisieren. Das Beschriftungsproblem lässt sich ganz allgemein als kombinatorisches Entscheidungsproblem ausdrücken: Gegeben eine Menge von zu beschriftenden Elementen einer Grafik und zu jedem Element eine Menge von Beschriftungskandidaten, ist es möglich, jedem Element einen Kandidaten aus der betreffenden Menge zuzuordnen, ohne dass sich zwei der gewählten Kandidaten schneiden?

Leider muss man davon ausgehen, dass dieses Problem im allgemeinen nicht effizient zu entscheiden ist. Daher haben fast alle bisherigen Arbeiten zu diesem Thema heuristische oder approximative Verfahren für entsprechende Optimierungsprobleme vorgeschlagen, etwa um eine Beschriftung einer möglichst großen Teilmenge der Grafikelemente zu finden. Dieses Problem bezeichnet man als das Anzahlmaximierungsproblem.

In meiner Dissertation nähere ich mich dem Beschriftungsproblem von zwei Seiten. Einerseits stelle ich ein theoretisches Gerüst auf, mit dessen Hilfe man das Anzahlmaximierungsproblem für endliche Kandidatenmengen gut formulieren und effiziente Algorithmen angeben kann, die den Suchraum für eine optimale Lösung erheblich verkleinern. Dieses Gerüst verallgemeinert das klassische Constraint-Satisfaction-Problem. Ich gebe einen solchen Algorithmus sowie eine einfache Heuristik an, die auf diesen Algorithmus aufbaut und in der Praxis sehr gute Resultate liefert.

Andererseits beschäftige ich mich mit Spezialfällen des Beschriftungsproblems. Ich habe mich zuerst mit der Beschriftung von Punkten mit achsenparallelen Rechtecken befasst, wobei für jeden Punkt die vier klassischen Positionen zugelassen wurden, also die, bei denen eine Ecke der Beschriftung den betreffenden Punkt berühren muss. Auf dieses Spezialproblem habe ich den erwähnten allgemeinen Algorithmus angewandt und mit anderen Verfahren experimentell verglichen. Dann habe ich mich mit Beschriftungsmodellen beschäftigt, in denen eine unendliche Anzahl von Beschriftungskandidaten zugelassen wird. Ich konnte zeigen, dass man nicht erwarten kann, obiges Entscheidungsproblem für quadratische oder kreisförmige Beschriftungen effizient zu lösen, falls jede Beschriftung ihren Punkt berühren muss. Trotzdem habe ich effiziente Algorithmen für Optimierungsversionen beider Probleme gefunden. Für achsenparallele rechteckige Beschriftungen gleicher Höhe stelle ich ein Approximationsschema für das Anzahlmaximierungsproblem vor. Andererseits zeige ich, dass man nicht erwarten kann, ein solches Schema für die Maximierung der Größe kreisförmiger Beschriftungen zu finden.

Ausser der Beschriftung von Punkten untersuche ich das Problem, wie man Linienzüge, also Flüsse oder Straßen, qualitativ hochwertig beschriften kann. Dies ist im Gegensatz zur Punktbeschriftung, wo die Zielfunktion meist klar ist, eher ein Modellierungsproblem, bei dem man die Anformderungen der Kartographen erst herausfinden muss. Ich habe diese dann in harte und weiche Anforderungen eingeteilt und einen effizienten Algorithmus vorgeschlagen, der garantiert, die harten Anforderungen zu erfüllen, und der innerhalb eines Teils des Suchraums die weichen Anforderungen soweit wie möglich optimiert.

Um die Praxisrelevanz meiner Untersuchungen zu unterstreichen, sind die meisten angegebenen Algorithmen implementiert worden. Dabei bin ich auf das schon bekannte Paradigma des generischen Programmierens gestoßen, das es ermöglicht, Programme sehr allgemein und flexibel zu halten. Ich zeige, wie man damit erfolgreich geometrische Algorithmen entwirft.