Analyse von inhomogenen Unterteilungsalgorithmen

Unterteilungsalgorithmen bieten ein mathematisches Werkzeug für Computeranimation, Signal und Bildverarbeitung,Internetübertragung vongeometrischenDaten.Die Theorie von Unterteilungsalgorithmen ist die mathematische Theorie der algorithmischen Erzeugung von Kurven und Oberflächen. Die zugrundeliegenden Algorithmen sind rekursiv und erzeugen dichter werdende Punktmengen, normalerweise in der Ebene oder im dreidimensionalen Raum. Diese Punktmengen bilden die Eckpunkte von Polygonzügen oder Gittern, die im Idealfall gegen Kurven oder Oberflächen konvergieren. Die wichtigsten erforderlichen Eigenschaften solcher Kurven oder Oberflächen sind ihre Form und Glattheit. Im Fall von homogenen Daten werden diese Eigenschaften mittels Matrixtechniken (gemeinsamer Spektralradius) vollständig charakterisiert. Hingegen ist es immer noch eine offeneFrage, obähnlicheCharakterisierungen im Fall voninhomogenen Unterteilungsalgorithmen überhaupt möglich sind. Dieses Projekt soll entweder eine positive Antwort auf diese Frage geben und damit die Stärker der Matrixtechniken nachweisen, oder aber ihr begrenzte Anwendbarkeit und Aussagefähigkeit demonstrieren. EinerfolgreicherAbschlußdieses Projekts wirddieAnalysevon inhomogenen Unterteilungsalgorithmen vereinfachen und neue, durch Anwendungen vorgegebene Konstruktionen solcher Unterteilungsalgorithmen ermöglichen.

Unterteilungsalgorithmen sind rekursive Verfahren, die zur automatisierten Erstellung von Kurven und Flächen verwendet werden. Unterteilungsalgorithmen werden z.B. in der Computeranimation, in der Signal- und Bildverarbeitung und bei der Internetübertragung von geometrischen Daten verwendet. Das Projekt ``Analyse von inhomogenen Unterteilungsalgorithmen" beschäftigte sich mit grundlegenden Eigenschaften von Unterteilungsalgorithmen sowie mit der Konvergenz, Glattheit und den geometrische Eigenschaften von erzeugten Kurven und Flächen. Im Rahmen dieses Projekts hat es uns gelungen, die Hölder-Regularität von anisotropischen, multivariaten Unterteilungsalgorithmen mit Hilfe des gemeinsamen, richtungsabhängigen Spektralradius von endlichen Matrixmengen zu charakterisieren. Dieses Resultat liefert die Lösung eines 25 Jahre alten Problems in der Approximationstheorie. Die Matrixmengen, die zur Berechnung des gemeinsamen Spektralradius benutzt werden, wurden bisher manuell konstruiert. Wir entwickelten den ersten, leicht programmierbaren Algorithmus zur Konstruktion der entsprechenden Matrixmengen. Diese Methode und unser Modifizierte-Invariante-Polytop-Algorithmus bilden die Grundlage eines benutzerfreundlichen Programms zur Bestimmung der Glattheit von Kurven und Flächen. Diese Software ist auch unverzichtbar für Berechnungen des gemeinsamen Spektralradius bei Kode-Konstruktion in der Kodierungstheorie oder bei der Feststellung der Eigenschaften von {\it switched linear systems}. Neben der Glattheit von Unterteilungsalgorithmen ist auch die Vielvalt von geometrischen Formen, die diese Algorithmen produzieren können, von besonderer praktischer Bedeutung. Wir haben Charakterisierungen solcher geometrischen Formen in mehreren Spezialfällen von inhomogenen Unterteilungsalgorithmen gefunden.