Institut für Theoretische Informatik, Algorithmik

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

Kontakt