Rechteckszerlegungen: Neue Ansätze sollen Fortschritte bringen

Eine Rechteckszerlegung ist eine Unterteilung eines Rechtecks in endlich viele Rechtecke. Rechteckszerlegungen wurden in den vergangenen Jahren von zahlreichen Forschungsteams eingehend untersucht. Beiträge dieser Forschungsrichtung kamen aus zahlreichen Teildisziplinen von Mathematik und Informatik. Anwendungsfälle finden sich z. B. bei der Gestaltung von integrierten Schaltkreisen und bei der Visualisierung von wissenschaftlichen Daten. Andrei Asinowski, Forscher im Bereich der Kombinatorik am Institut für Mathematik, wird nun in einem FWF-Projekt offene Forschungsprobleme dazu lösen.

„Kombinatorisch gesehen sind Rechteckszerlegungen eine sehr natürliche und interessante Struktur. Sie sind mit vielen anderen kombinatorischen und algebraischen Objekten eng verwandt“, erklärt Andrei Asinowski, Mathematiker an der Universität Klagenfurt. Dazu zählen u. a. Bäume, Gitterpfade oder Klassen von Permutationen. Rechteckszerlegungen sind für verschiedene Anwendungsbeispiele aus Sicht der algorithmischen Geometrie interessant: „Sie werden beispielsweise als grundlegendes Modell für das Layout von integrierten Schaltkreisen oder für die Kartenanamorphoten verwendet. Außerdem spielen sie eine wichtige Rolle in den theoretischen Grundlagen der architektonischen Gestaltung. Schließlich kommen sie häufig in der Unterhaltungsmathematik und in der Kunst vor.“

Die kombinatorische Analyse der Rechteckszerlegungen ist ausgesprochen anspruchsvoll, wobei viele Fragestellungen bisher nur für einige Sonderfälle beantwortet werden können. Andrei Asinowski erklärt weiter: „Deshalb planen wir, in diesem Projekt einige strukturelle Aspekte von Rechteckszerlegungen sowie damit verwandte Abzählungsprobleme zu untersuchen.“

Methodisch wird der Forscher auf die strukturelle Analyse und auf moderne Methoden aus der analytischen und abzählenden Kombinatorik zurückgreifen. „Dieses Projekt soll insbesondere das große Potenzial zeigen, das die analytische Kombinatorik hat, wenn es um das Lösen von Problemen aus der theoretischen Informatik geht“, fasst Asinowski zusammen.