Parallele Algorithmen in der algorithmischen Geometrie mit dem Schwerpunkt auf Mustererkennung

• Antragsteller: Professor Dr. Helmut Alt
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2010 bis 2016
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 166649592

In Rahmen dieses Forschungsvorhabens soll ein Rechenmodell für parallele Algorithmen entwickelt werden, das sowohl realistisch den Möglichkeiten der aktuellen parallelen Hardware entspricht und die absehbare Entwicklung in der näheren Zukunft berücksichtigt, als auch theoretisch fundiert ist und damit eine solide Grundlage für die Entwicklung und Analyse von Algorithmen bietet. Unter Beachtung dieses Modells sollen effiziente parallele Algorithmen für Probleme der algorithmischen Geometrie entwickelt werden. Dabei liegt der Schwerpunkt unserer Forschung im Bereich der geometrischen Mustererkennung und des Vergleichs und der Analyse von Formen. Durch die Arbeit der letzen Jahre haben wir dieses Gebiet gründlich erforscht und durch eigene Arbeiten zu dessen Weiterentwicklung beigetragen. Zum Berechnen von etablierten Abstandsmaßen für geometrische Formen, wie z.B. des Hausdorff- oder des Frechet-Abstands, sind effiziente sequentielle Algorithmen entwickelt worden. Die Parallelisierung dieser Algorithmen ist nicht trivial und soll zunächst untersucht werden. Mit den gewonnenen Erkenntnissen sollen dann neue effiziente parallele Algorithmen entwickelt oder die bereits bekannten parallelisiert werden. Zusätzlich sollen allgemeinere Probleme der algorithmischen Geometrie und Algorithmenentwurfstechniken, die als Bausteine in den Algorithmen zur geometrischen Mustererkennung häufig vorkommen, auf ihre Parallelisierbarkeit hin überprüft werden und effiziente Algorithmen unter Berücksichtigung des neuen Rechenmodells entwickelt werden. Typische Beispiele für solche Probleme und Techniken sind die Berechnung von Arrangements, Clustering, Sweepline-Techniken, und dynamisches Programmieren, wobei letzteres nicht nur auf geometrische Probleme beschränkt ist. Einige dieser Techniken, wie z.B. Sweepline oder dynamisches Programmieren, scheinen in allgemeiner Form schwer parallelisierbar zu sein. Daher ist es eventuell sinnvoll neue parallele Algorithmen für spezielle Anwendungen dieser Paradigma zu entwickeln. Ein wesentlicher Bestandteil des Projekts soll die Implementierung der entwickelten Algorithmen auf existierender Hardware (Multicore-Rechner, GPGPU-Grafikkarten) sein.

• DFG-Verfahren: Sachbeihilfen