Algorithmen zur Konturbeschriftung
Studien- oder Diplomarbeit
Beschriftungsprobleme treten in vielen Anwendungsfeldern auf, in denen Merkmale in Illustrationen durch Namen oder kurze Erklärungen beschriftet werden. Beispiele sind Landkarten, technische Zeichnungen, Datenvisualisierung usw. Sind die Merkmale sehr dicht angeordnet, können sie wegen des fehlenden Platzes nicht alle gleichzeitig beschriftet werden. Eine Alternative ist es die Beschriftungen am Rand der Zeichnung zu platzieren und mit Pfeilen den Merkmalen zuzuordnen. Bislang wurde dieses Problem nur für rechteckige Zeichnungen betrachtet. In der Studien-/Diplomarbeit sollen allgemeinere Konturen als Rand der Zeichnung betrachtet werden und die Beschriftungen optimal entlang dieser Konturen platziert werden. Ein typisches Optimierungskriterium ist z.B. die Gesamtlänge der Beschriftungspfeile zu minimieren.
Art
Studien- oder Diplomarbeit
Ziele
Einarbeitung in die existierende Literatur zu verwandten Themen; Entwurf, Implementierung und experimentelle Analyse von effizienten Algorithmen für geeignete Problemvarianten (Umfang je nach Art der Arbeit).
Voraussetzung
fundierte algorithmische Kenntnisse und Interesse für geometrische Fragestellungen