Clustering und Triangulierungsprobleme

Forschungsprojekt P 14755 Clustering und TriangulierungsproblemeFranz AURENHAMMER27.11.2000 Ziel dieses Projektes ist es, neue Methoden zum Clustern und Triangulieren von Datenpunktmengen zu entwickeln. Clustern einer Datenmenge bedeutet, die Daten in Gruppen (Cluster) zu teilen, sodaß die Daten innerhalb einer Gruppe ähnlich sind, und Daten aus verschiedenen Gruppen unähnlich, bezüglich eines vorgegebenen Maßes. Triangulieren einer Punktemenge in der Euklidischen Ebene bedeutet, ein Dreiecksgitter zu erzeugen, das alle Punkte der Menge (und nur diese) verwendet, und das bezüglich eines gegebenen Kriteriums optimal ist. Beide Probleme gehören zur Klasse der geometrischen Optimierungsprobleme und sind teilweise verwandt. Trotz der beachtenswerten internationalen Aufmerksamkeit, die diesem Problemkreis geschenkt wurde, sind praktisch effiziente Lösungen in gewissen Fällen schwer zu erhalten (etwa Näherungen für NP-schwere Clusterprobleme, oder für uniforme Triangulierungen) bzw. ist der Komplexitätsstatus ungeklärt (etwa für minimum-weight Triangulierungen). Im Projekt ist beabsichtigt, kombinatorische und geometrische Eigenschaften solcher Probleme zu untersuchen, mit dem Ziel, praktisch effiziente Algorithmen zu erhalten. Konkret werden u.a. folgende Themen behandelt. (1) Morphen von Spannbäumen mittels Delaunay Triangulierungen, unter Verwendung einer in unseren Vorarbeiten entwickelten Methode. Zu untersuchende Anwendungen sind das Clustern vorseparierter Punktemengen, Kompression von Dreiecksgittern und Morphen graphischer Objekte. (2) Entscheiden der Existenz von kompatiblen Triangulierungen für zwei gegebene Punktemengen. Ein Resultat dieser Art würde, abgesehen vom theoretischen Wert, einen allgemeinen Algorithmus zum Morphen graphischer Objekte ermöglichen. In unseren Vorarbeiten wurde das Resultat für kleine Punktemengen bzw. für Mengen mit wenigen inneren Punkten bewiesen. (3) Optimale Triangulierungen. Die zwei Paradebeispiele optimaler Triangulierungen, die Delaunay und die Minimum-Weight, haben in gewissen Anwendungen Nachteile. Als Alternative betrachten wir Minimum-Streß Triangulierungen, wobei der Streß eines Datenpunktes eine geeignete Funktion seiner Nachbarn in der Triangulierung ist. Dieses Konzept simuliert, soweit als möglich, einen Gleichgewichtszustand in den Punkten, und erscheint als vielversprechender Kandidat für Qualitäts-Dreiecksnetze.