Logo der Fakultät Logo LG Theoretische Informatik
 

Diplomarbeit

Illustration

Zeichnen von Bäumen auf dem Gitter mit wenigen Segmenten

Verfasser: Gregor Hültenschmidt
Betreuer/in: Philipp Kindermann
Status: abgeschlossen
Jahr: 2016
Beschreibung: Ziel dieser Arbeit ist es, einen Algorithmus zum Zeichnen von Bäumen zu entwerfen. Dabei sollen zwei Ziele von der erstellten Zeichnung erfüllt werden: (1) Es soll nur eine kleine Anzahl von Segmenten benutzt werden (man kann mehrere Kanten als ein Segment zeichnen, wenn sie in einer Linie stehen). (2) Die Zeichnung soll auf einem kleinem Gitter realisiert werden (es sollen also nur polynomielle ganzzahlige Koordinaten verwendet werden). Zum Erreichen dieser Ziele soll die 'heavy path decomposition' Technik eingesetzt werden. Der Algorithmus soll auch prototypisch implementiert werden.
01.03.2017
FernUni-Logo FernUniversität in Hagen, LG Theoretische Informatik, 58084 Hagen