Eine der Ähnlichkeitsbestimmung verwandte Frage ist die Approximation oder Vereinfachung von Formen, wobei es darum geht, eine vorgegebene Form durch eine möglichst einfache Form gut zu approximieren, z.B. ein Polygon mit vielen Ecken durch eines mit wenigen.
Weiterhin gehören zu diesem Problemkreis Probleme der Symmetriebestimmung, dh. von gegebenen Figuren oder Punktmustern die Symmetriegruppe zu berechnen.
Ziel unseres Projektes ist es, diese Problemstellungen mit Mitteln der algorithmischen Geometrie zu behandeln. Es geht also zum einen darum, Algorithmen zur Ähnlichkeitsmessung zu entwickeln, die es erlauben, effizient einen kleinsten Abstand zwischen Figuren in der Ebene oder im Raum unter den erlaubten Matching-Transformationen zu berechnen. Zunächst stellt sich die Frage, welches Abstandsmaß zur Messung der Ähnlichkeit geeignet ist. Wit betrachten dabei insbesondere den Hausdorffabstand oder die Fläche der symmetrischen Differenz zweier Figuren. Wenn man den Abstand von Kurven in Raum und Ebene oder Flächen im Raum berechnen möchte bietet sich auch die Fréchet-Metrik an, die für einige Beispiele ein adäquateres Maß ist als der Hausdorff-Abstand, dafür ist sie aber auch wesentlich schwerer zu berechnen.
Approximationsprobleme und Matchingprobleme lassen sich im allgemeinen auf das folgende Grundproblem zurückführen:
Eine Übersicht über die wichtigsten bisherigen Arbeiten zu dem genannten Themenkreis wird in [AG] gegeben. Dieser Artikel ist als ein Kapitel im geplanten Handbook on Computational Geometry vorgesehen.
Matching von Formen mit Referenzpunktmethoden.
Um approximative Lösungen zu finden, haben wir insbesondere die früher von uns entwickelte Idee der Referenzpunktmethoden weiterentwickelt. Ein Referenzpunkt ist ein fester, einer Figur zugeordneter Punkt mit der Eigenschaft, daß beim optimalen Matching zweier Figuren auch die beiden Referenzpunkte nahe zusammenliegen. Umgekehrt kann man eine approximative Lösung dadurch finden, daß man zunächst die beiden Referenzpunkte aufeinander abbildet und dann die optimale Lösung unter Fixierung dieser Referenzpunkte bestimmt. Diese ist meist viel einfacher zu berechnen als das uneingeschränkte Optimum.
In [AAR] haben wir gezeigt, daß für Matching beliebiger kompakter Formen in beliebigen Dimensionen unter Translationen, starren Bewegungen oder Ähnlichkeitsabbildungen bezüglich des Hausdorff-Abstands der aus der konvexen Geometrie bekannte Steiner-Punkt ein Referenzpunkt ist. Dies liefert direkt effiziente approximative Algorithmen für das Matchingproblem zum Beispiel von einfachen Polygonen in der Ebene oder von Polyedern im dreidimensionalen Raum.
In [AFRW] zeigen wir, daß der Schwerpunkt einer konvexen Menge in zwei Dimensionen einen Referenzpunkt für die symmetrische Differenz als Abstandsmaß unter den oben genannten Transformationsklassen und auch für beliebige affine Abbildungen darstellt und damit effektive Matching-Verfahren zur Verfügung stehen. In dieser Arbeit wird somit einerseits ein Beitrag zur konvexen Geomtrie geliefert und andererseits werden effiziente Algorithmen für die Anwendung enwickelt.
In [AHS] wird eine mit dem Approximationsproblem verwandte Fragestellung betrachtet, nämlich für ein gegebenes konvexes Polygon das flächengrößte inbeschriebene Rechteck zu finden. Durch eine Erweiterung der Technik des tentative prune-and-search erhalten wir einen Algorithmus logarithmischer Laufzeit.
Symmetrieprobleme werden in zwei Diplomarbeiten bearbeitet:
A. Papenberg beschäftigt sich mit Verfahren zur Bestimmung der Friesgruppe eines Frieses, von dem ein endlicher Ausschnitt vorliegt. Dabei gilt es, ein Grundmuster zu finden, aus dem durch durch periodische Wiederholung das Fries hervorgeht, und eventuelle Symmetrien dieses Grundmusters zu bestimmen. Insbesondere wird das Problem auch für ungenaue Eingabedaten untersucht. Das Verfahren wurde implementiert.
Ziel der Arbeit von S. Oesterreicher ist das Erzeugen von Beispielen der planaren Symmetriegruppen mittels D0L-Systemen, einer speziellen Form von L-System, und umgekehrt, das Erkennen von Symmetrien anhand der die Objekte erzeugenden Grammatiken. Aus dieser Arbeit ist ein Graphikprogramm entstanden, das ein gegebenes Grundmuster zu einem Objekt in jeder beliebigen Symmetriegruppe vervielfältigt.
Die Programme für beide Arbeiten können auf Anfrage zur Verfügung gestellt werden.
In einem gemeinsamen Projekt mit Archäologen der FU Berlin geht es darum, große Mengen von keramischen Fundstücken (hauptsächlich aus dem 6. und 7. Jahrhundert v. Chr.) formtypologisch zu klassifizieren. Die Querschnitte der Fundstücke stellen zweidimensionale Kurven dar, von denen wir zuerst polygonale Approximationen berechnen. Mit Hilfe von Algorithmen zur Ähnlichkeitsmessung werden diese Kurven bzw. deren Approximationen miteinander verglichen. Eine Clusteranalyse soll dann die gewünschte Klassifikation liefern. Dieses Projekt ist Gegenstand der Dissertation von U. Fuchs. Programmierarbeiten werden von studentischen Hilfskräften und Diplomanden geleistet.
Michael Godau untersucht in seiner Dissertation Verfahren zur Berechnung der Fréchet-Metrik. Dabei stellt sich heraus, daß das exakte Problem im Dreidimensionalen NP-vollständig ist und auch hier approximative Lösungen gesucht werden müssen.
Im Rahmen einer Diplomarbeit (L. Knipping) sollen die vorher beschriebenen Referenzpunktmethoden implementiert werden. Weiterhin arbeitet die Gruppe an einer möglichen Erweiterung dieser Methoden. Insbesondere wird untersucht, ob es für gewisse Matching-Probleme andere Referenzobjekte als Punkte, also z.B. Strecken, gibt. Durch das Matching dieser Objekte könnte möglicherweise die Zahl der Freiheitsgrade für das Optimierungsproblem noch weiter reduziert und damit noch effizientere Algorithmen gefunden werden.
D. Knauth beschäftigt sich in seiner Diplomarbeit mit dem Matching von Punktmustern unter allgemeinen affinen Abbildungen. Insbesondere ist auch an Implementierungen gedacht und die Behandlung der dabei auftauchenden numerischen Probleme.