´

TOPCOM

Triangulierungen_Symmetrien
14 mögliche Zerlegungen eines Sechsecks in Dreiecke.

Das vom Lehrstuhlinhaber entwickelte und frei verfügbare Programmpaket TOPCOM ist das momentan weltweit schnellste Programm zur Enumeration von Triangulierungen in beliebigen Dimensionen. Ein Lehrbuch zu diesem Thema mit den internationalen Partnern Jesús de Loera und Francisco Santos ist kurz vor der Fertigstellung. Diese Triangulierungen haben auch eine Bedeutung in der Optimierung: Sie geben für ein Lineares Programm die Datenbereiche an, innerhalb derer sich die Struktur einer Optimallösung nicht ändert.

Die nebenstehende Grafik verdeutlicht das prinzipielle Vorgehen der Software TOPCOM: Bis auf Symmetrie sind nur drei der abgebildeten Triangulierungen nicht identisch. Diese Beobachtung wird zur Enumeration sehr viel größerer Mengen ausgenutzt. Im Bild sind zwei Triangulierungen benachbart, wenn sie durch Austausch einer Diagonalen in einem Viereck auseinander hervorgehen. Der entstehende Graph ist hier übrigens der Kantengraph eines Polytops, welches in der parametrischen Linearen Optimierung eine Rolle spielt.

Weitere Informationen und Downloads finden sich auf Prof. Dr. Jörg Rambaus persönlicher Homepage.

Universität Bayreuth -