Point Labeling with Leaders for Convex Boundaries
Neil Jami · 2012
This diploma thesis deals with the concept of convex boundary labeling. Given a set of points positioned in a map with a polygonal shape, the objective is to place, for each point, a rectangular label outside of the map, and connect it to the point with a leader. Generally, the labels are placed so that no two leaders intersect and so that the total leader length is minimized. The main contribution of this work is the study of boundary labelings for maps with a convex polygonal shape. We consider axis aligned leaders with at most one bend, and assume that the labels can be placed anywhere to the right of the map. We study here three different models of the problem and present different algorithms to compute a crossing-free labeling with minimum leader length. We describe the different algorithms and prove their correctness. The algorithms for the different models have a similar structure. They first compute a labeling with minimal leader length. For this purpose, each algorithm calls repetitively a second algorithm that computes a labeling with minimal leader length for a cluster of labels. In two of the three models, the second algorithm computes minimum weighted matchings. Since computing a matching takes a long time, we look for an alternative fast algorithm to avoid matching computations as much as possible. In a second step, the algorithms remove the remaining leader crossings in the computed labeling. Finally, we evaluate the quality and the performance of the implemented algorithms for practical inputs. Deutsche Zusammenfassung Diese Diplomarbeit beschaftigt sich mit dem Konzept von konvexer Randbeschriftungen. Gegeben eine Menge von Punkten in einer von einem Polygon begrenzten Karte, ist das Ziel, fur jeden Punkt ein Label mit rechteckiger Form auserhalb des Polygons zu platzieren und durch einen Pfeil (Leader) mit dem Punkt zu verbinden. Somit werden Punkte in einer Karte annotiert. Ublicherweise werden die Labels so positioniert, dass die Leaders sich nicht kreuzen und die gesamte Leaderlange minimiert wird. Das Hauptthema in dieser Arbeit ist die Untersuchung von Algorithmen fur konvexeRandbeschriftungen. Wir betrachten hier Leader, die aus hochstens zwei horizontalen oder vertikalen Segmente bestehen. Auserdem werden die Label rechts von der Karte platziert. Wir untersuchen hier drei Labeling Modelle und die entsprechenden Algorithmen, die kreuzungfreie Labelings mit minimaler Leaderlange berechnen. Wir beschreiben die verschiedenen Algorithmen und beweisen ihre Korrektheit. Die drei Algorithmen haben dieselbe Grundstruktur. Zunachst wird ein Labeling mit minimaler Leaderlange berechnet, indem jeder Algorithmus iterativ einen weiteren Algorithmus aufruft, der ein Labeling eines einzigen Clusters mit minimaler Leaderlange berechnet. Das Labeling eines Clusters wird in zwei der drei Modelle mithilfe von Matchings mit minimalem Gewicht berechnet. Da die Laufzeit von Matchingalgorithmen ziemlich hoch ist, wird eine schnellere Losung benutzt, um so selten wie moglich einen Matchingalgorithmus aufzurufen. In einem zweiten Schritt entfernt jeder Algorithmus die eventuell vorhandenen Kreuzungen von dem Labeling minimaler Leaderlange. Schlieslich werden die Algorithmen implementiert, um ihre Laufzeit und Qualitat fur praktische Instanzen zu evaluieren.